# Make the XOR of All Segments Equal to Zero
**Difficulty:** HARD
[External](https://leetcode.com/problems/make-the-xor-of-all-segments-equal-to-zero)
Canonical: https://scaleengineer.com/dsa/problems/make-the-xor-of-all-segments-equal-to-zero
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
**Companies:** [Media.net](https://scaleengineer.com/companies/media.net)
---
## Problem
You are given an array `nums`​​​ and an integer `k`​​​​​. The XOR of a segment `[left, right]` where `left <= right` is the `XOR` of all the elements with indices between `left` and `right`, inclusive: `nums[left] XOR nums[left+1] XOR ... XOR nums[right]`.

Return _the minimum number of elements to change in the array_ such that the `XOR` of all segments of size `k`​​​​​​ is equal to zero.

**Example 1:**

**Input:** nums = [1,2,0,3,0], k = 1
**Output:** 3
**Explanation:** Modify the array from [**1**,**2**,0,**3**,0] to from [**0**,**0**,0,**0**,0].

**Example 2:**

**Input:** nums = [3,4,5,2,1,7,3,4,7], k = 3
**Output:** 3
**Explanation:** Modify the array from [3,4,**5**,**2**,**1**,7,3,4,7] to [3,4,**7**,**3**,**4**,7,3,4,7].

**Example 3:**

**Input:** nums = [1,2,4,1,2,5,1,2,6], k = 3
**Output:** 3
**Explanation:** Modify the array from [1,2,**4,**1,2,**5**,1,2,**6**] to [1,2,**3**,1,2,**3**,1,2,**3**].

**Constraints:**

* `1 <= k <= nums.length <= 2000`
* `​​​​​​0 <= nums[i] < 210`

# Approaches
## Naive Dynamic Programming
The first key insight is to understand the condition that the XOR sum of all segments of size `k` is zero. If `nums[i] ^ ... ^ nums[i+k-1] = 0` and `nums[i+1] ^ ... ^ nums[i+k] = 0`, XORing these two equations gives `nums[i] ^ nums[i+k] = 0`, which means `nums[i] = nums[i+k]`. This implies the array must be periodic with period `k`. All elements at indices `j, j+k, j+2k, ...` must be identical.

This reduces the problem to partitioning the array into `k` groups based on `index % k`. For each group `i`, we must choose a single value `v_i` to change all its elements to. The cost for group `i` is the number of elements not equal to `v_i`. The chosen values must also satisfy `v_0 ^ v_1 ^ ... ^ v_{k-1} = 0`.

This structure lends itself to a dynamic programming solution. We can build up the solution one group at a time. Let `dp[i][j]` be the minimum cost to modify the first `i` groups such that the XOR sum of their chosen values is `j`. We can compute `dp[i][j]` by considering all possible values for the `i`-th group and using the results from `dp[i-1]`.
**Time:** O(n + k * 2^10 * 2^10). `O(n)` for pre-calculating frequencies. The DP calculation involves iterating `k` times. In each iteration, we have a nested loop over the `1024` possible XOR sums and `1024` possible values for the current group. This results in `O(k * 1024 * 1024)`, which is too slow for the given constraints. · **Space:** O(n + 1024). We need `O(n)` space to store the frequency maps for all `k` groups in the worst case. The DP table requires `O(k * 1024)`, but with space optimization, it becomes `O(1024)`.
**Pros:** Relatively simple to understand as it's a direct translation of the recurrence relation.; Correctly models the problem's state transitions.
**Cons:** The time complexity is very high due to the triple nested loop structure (`k * 1024 * 1024`), making it too slow for the given constraints.
### Explanation
This approach uses a straightforward dynamic programming formulation. We define `dp[i][j]` as the minimum changes needed for the first `i` groups (0 to `i-1`) to have their chosen values' XOR sum equal to `j`.

We can use a 2D DP table of size `(k+1) x 1024`. The state transition is as follows: to calculate `dp[i][j]`, we consider every possible value `v` (from 0 to 1023) that we can assign to group `i-1`. The cost of assigning `v` to group `i-1` is `size_{i-1} - freq_{i-1}[v]`. If we choose `v`, then the XOR sum of the first `i-1` groups must have been `j ^ v`. So, we look up `dp[i-1][j ^ v]`, add the cost for the current group, and take the minimum over all possible `v`.

To save space, we can notice that `dp[i]` only depends on `dp[i-1]`. Thus, we can use only two arrays, one for the previous state and one for the current state, reducing space complexity.

```java
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int minChanges(int[] nums, int k) {
        int n = nums.length;
        int MAXXOR = 1 << 10;
        int INF = (int) 1e9;

        // Group elements and get frequencies
        Map<Integer, Integer>[] freqs = new HashMap[k];
        int[] groupSizes = new int[k];
        for (int i = 0; i < k; i++) {
            freqs[i] = new HashMap<>();
        }
        for (int i = 0; i < n; i++) {
            int groupIdx = i % k;
            freqs[groupIdx].put(nums[i], freqs[groupIdx].getOrDefault(nums[i], 0) + 1);
            groupSizes[groupIdx]++;
        }

        // DP state: dp[j] = min changes for groups processed so far to have XOR sum j
        int[] dp = new int[MAXXOR];
        Arrays.fill(dp, INF);
        dp[0] = 0; // Base case: 0 groups, XOR sum 0, 0 changes

        for (int i = 0; i < k; i++) {
            int[] nextDp = new int[MAXXOR];
            Arrays.fill(nextDp, INF);
            // Iterate over all possible previous XOR sums
            for (int j = 0; j < MAXXOR; j++) {
                if (dp[j] == INF) continue;
                // Iterate over all possible values `v` to set for the current group `i`
                for (int v = 0; v < MAXXOR; v++) {
                    int costToChange = groupSizes[i] - freqs[i].getOrDefault(v, 0);
                    int newXor = j ^ v;
                    nextDp[newXor] = Math.min(nextDp[newXor], dp[j] + costToChange);
                }
            }
            dp = nextDp;
        }

        return dp[0];
    }
}
```
### Algorithm
- The core condition `XOR of all segments of size k is zero` implies that `nums[i] = nums[i+k]` for all `0 <= i < n-k`. This means the array must be periodic with period `k`.
- This property partitions the array indices into `k` groups based on `index % k`. All elements within the same group must be changed to an identical value.
- Additionally, the chosen values for each group, let's call them `v_0, v_1, ..., v_{k-1}`, must satisfy `v_0 ^ v_1 ^ ... ^ v_{k-1} = 0`.
- The problem is now to select `v_0, ..., v_{k-1}` to minimize the total number of changes, subject to the XOR sum constraint.
- We can solve this using dynamic programming. Let `dp[i][j]` be the minimum number of changes for the first `i` groups (from group 0 to `i-1`) such that the XOR sum of their chosen values is `j`.
- **State:** `dp[i][j]` = minimum changes for groups `0, ..., i-1` to have an XOR sum of `j`.
- **Initialization:** `dp[0][0] = 0`, and `dp[0][j] = infinity` for `j > 0`.
- **Transition:** To compute `dp[i][j]`, we iterate through all possible values `v` (from 0 to 1023) for group `i-1`. If we choose `v` for group `i-1`, the XOR sum of the first `i-1` groups must have been `j ^ v`. The cost for changing group `i-1` to `v` is `size_{i-1} - freq_{i-1}[v]`, where `size_{i-1}` is the number of elements in the group and `freq_{i-1}[v]` is the frequency of `v` in that group.
- The recurrence relation is: `dp[i][j] = min_{0 <= v < 1024} (dp[i-1][j ^ v] + cost(i-1, v))`.
- **Final Answer:** The minimum changes for all `k` groups to have an XOR sum of 0 is `dp[k][0]`.

## Optimized Dynamic Programming
This approach builds upon the naive DP solution by optimizing the state transition. The bottleneck in the naive approach is the inner loop that iterates through all 1024 possible values `v` for the current group. We can observe that the cost function `cost(group, v) = size_{group} - freq_{group}[v]` behaves differently for values `v` that are present in the group versus those that are not.

For any value `v` not present in the group, `freq_{group}[v]` is 0, and the cost is simply `size_{group}`. The total cost for this case would be `dp[i-1][j^v] + size_{group}`. We can achieve a minimum cost for this case by choosing `v` such that `dp[i-1][j^v]` is minimized. The minimum value in the `dp[i-1]` array is `min_prev_dp = min(dp[i-1])`. So, we can establish a baseline cost for `dp[i][j]` as `min_prev_dp + size_{group}`.

After setting this baseline, we only need to consider the special cases where `v` was already present in the group. For these values, the cost is lower than `size_{group}`. We iterate only through this much smaller set of existing values and update the DP state if we find a cheaper way to achieve the target XOR sum `j`.
**Time:** O(n * 1024). `O(n)` for pre-computation. The DP part consists of `k` iterations. Each iteration involves finding the minimum in the DP array (`O(1024)`) and then updating the next DP array. The update step takes `O(d_i * 1024)`, where `d_i` is the number of distinct elements in group `i`. The total time is `O(n + k * 1024 + sum(d_i) * 1024)`. Since `sum(d_i)` over all groups is at most `n`, the total complexity is `O(n * 1024)`. · **Space:** O(n + 1024). `O(n)` for frequency maps and `O(1024)` for the DP array.
**Pros:** Significantly more efficient than the naive DP approach.; Feasible for the given constraints and passes within the time limit.
**Cons:** The logic is slightly more complex to implement compared to the naive version.
### Explanation
The core idea is to reduce the complexity of the DP transition. Instead of a triple loop, we can get by with two effective loops.

For each group `i` from `0` to `k-1`:
1.  Find the minimum cost from the previous step: `min_prev_dp = min(dp)`. This takes `O(1024)`.
2.  Create a `next_dp` array. We can initialize every entry `next_dp[j]` with a default high cost: `min_prev_dp + groupSizes[i]`. This represents the cost of changing all elements in group `i` to a new value that wasn't present before.
3.  Then, we iterate through only the numbers `v` that were originally in group `i`. For each such `v`, we calculate the specific cost `costToChange = groupSizes[i] - freqs[i][v]`. We then use this to potentially improve the `next_dp` values: for each previous XOR sum `p`, the new cost would be `dp[p] + costToChange` for the new XOR sum `p ^ v`. This can be written as iterating through all new XOR sums `j` and calculating `next_dp[j] = min(next_dp[j], dp[j ^ v] + costToChange)`.

This way, the innermost loop over all 1024 values is replaced by a loop over the distinct elements in the group, whose count is much smaller than 1024.

```java
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int minChanges(int[] nums, int k) {
        int n = nums.length;
        int MAXXOR = 1 << 10;
        int INF = (int) 1e9;

        // Step 1: Group elements and get frequencies
        Map<Integer, Integer>[] freqs = new HashMap[k];
        int[] groupSizes = new int[k];
        for (int i = 0; i < k; i++) {
            freqs[i] = new HashMap<>();
        }
        for (int i = 0; i < n; i++) {
            int groupIdx = i % k;
            freqs[groupIdx].put(nums[i], freqs[groupIdx].getOrDefault(nums[i], 0) + 1);
            groupSizes[groupIdx]++;
        }

        // Step 2: DP
        int[] dp = new int[MAXXOR];
        Arrays.fill(dp, INF);
        dp[0] = 0; // Base case

        for (int i = 0; i < k; i++) {
            // Find the minimum cost from the previous DP state
            int minPrevDp = INF;
            for (int val : dp) {
                minPrevDp = Math.min(minPrevDp, val);
            }
            if (minPrevDp == INF) continue;

            int[] nextDp = new int[MAXXOR];
            // Initialize with the cost of changing to a new number
            Arrays.fill(nextDp, minPrevDp + groupSizes[i]);
            
            // Iterate through existing numbers `v` in the current group `i`
            for (Map.Entry<Integer, Integer> entry : freqs[i].entrySet()) {
                int v = entry.getKey();
                int freq = entry.getValue();
                int costToChange = groupSizes[i] - freq;

                // Update DP states if choosing `v` is better
                for (int j = 0; j < MAXXOR; j++) {
                    if (dp[j] != INF) {
                        int newXor = j ^ v;
                        nextDp[newXor] = Math.min(nextDp[newXor], dp[j] + costToChange);
                    }
                }
            }
            dp = nextDp;
        }

        return dp[0];
    }
}
```
### Algorithm
- The approach starts with the same DP formulation: `dp[i][j]` is the minimum changes for the first `i` groups to have an XOR sum of `j`.
- The naive transition `dp[i][j] = min_{v} (dp[i-1][j ^ v] + cost(i-1, v))` is slow. We optimize it.
- We can rewrite the transition as `dp[i][j] = size_{i-1} + min_{v} (dp[i-1][j ^ v] - freq_{i-1}[v])`.
- We split the choice of `v` for group `i-1` into two cases:
  1. `v` is a value that was **not** originally present in group `i-1`. In this case, `freq_{i-1}[v] = 0`. The cost is `size_{i-1}`. To minimize the total cost, we should pick a `v` such that `j^v` corresponds to the state with the minimum cost in the previous DP row, `min_prev_dp = min(dp[i-1])`. This gives a baseline cost for `dp[i][j]` of `min_prev_dp + size_{i-1}`.
  2. `v` is a value that **was** originally present in group `i-1`.
- The optimized algorithm is as follows:
  1. For each DP iteration `i` from 1 to `k`:
  2. Find `min_prev_dp = min_{p=0..1023} dp[i-1][p]`.
  3. For each target XOR sum `j`, initialize `dp[i][j] = min_prev_dp + size_{i-1}`.
  4. Then, for each `j`, iterate only through the values `v` that were actually present in group `i-1` and update `dp[i][j]` if a better cost is found: `dp[i][j] = min(dp[i][j], dp[i-1][j ^ v] + size_{i-1} - freq_{i-1}[v])`.
- This avoids iterating through all 1024 possible values for `v`, instead only iterating through the distinct values present in the group, which is much smaller.

# Solutions
### Java

```java
class Solution {
public
  int minChanges(int[] nums, int k) {
    int n = 1 << 10;
    Map<Integer, Integer>[] cnt = new Map[k];
    Arrays.setAll(cnt, i->new HashMap<>());
    int[] size = new int[k];
    for (int i = 0; i < nums.length; ++i) {
      int j = i % k;
      cnt[j].merge(nums[i], 1, Integer : : sum);
      size[j]++;
    }
    int[] f = new int[n];
    final int inf = 1 << 30;
    Arrays.fill(f, inf);
    f[0] = 0;
    for (int i = 0; i < k; ++i) {
      int[] g = new int[n];
      Arrays.fill(g, min(f) + size[i]);
      for (int j = 0; j < n; ++j) {
        for (var e : cnt[i].entrySet()) {
          int v = e.getKey(), c = e.getValue();
          g[j] = Math.min(g[j], f[j ^ v] + size[i] - c);
        }
      }
      f = g;
    }
    return f[0];
  }
private
  int min(int[] arr) {
    int mi = arr[0];
    for (int v : arr) {
      mi = Math.min(mi, v);
    }
    return mi;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minChanges(vector<int> &nums, int k) {
    int n = 1 << 10;
    unordered_map<int, int> cnt[k];
    vector<int> size(k);
    for (int i = 0; i < nums.size(); ++i) {
      cnt[i % k][nums[i]]++;
      size[i % k]++;
    }
    vector<int> f(n, 1 << 30);
    f[0] = 0;
    for (int i = 0; i < k; ++i) {
      int mi = *min_element(f.begin(), f.end());
      vector<int> g(n, mi + size[i]);
      for (int j = 0; j < n; ++j) {
        for (auto &[v, c] : cnt[i]) {
          g[j] = min(g[j], f[j ^ v] + size[i] - c);
        }
      }
      f = move(g);
    }
    return f[0];
  }
};

```

### Python

```python
class Solution:
    def minChanges(self, nums: List[int], k: int) -> int: n = 1 << 10 cnt = [Counter() for _ in range(k)] size = [0] * k for i, v in enumerate(nums): cnt[i % k][v] += 1 size[i % k] += 1 f = [inf] * n f[0] = 0 for i in range(k): g = [min(f) + size[i]] * n for j in range(n): for v, c in cnt[i]. items(): g[j] = min(g[j], f[j ^ v] + size[i] - c) f = g return f[0]

```