Make the XOR of All Segments Equal to Zero

Hard

#1635Time: 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)`.1 company

Patterns

Dynamic Programming Bit Manipulation

Data structures

Array

Companies

Media.net

Prompt

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] < 2¹⁰

Approaches

2 approaches with complexity analysis and trade-offs.

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].

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].

Walkthrough

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.

1import java.util.Arrays;2import java.util.HashMap;3import java.util.Map;4 5class Solution {6    public int minChanges(int[] nums, int k) {7        int n = nums.length;8        int MAXXOR = 1 << 10;9        int INF = (int) 1e9;10 11        // Group elements and get frequencies12        Map<Integer, Integer>[] freqs = new HashMap[k];13        int[] groupSizes = new int[k];14        for (int i = 0; i < k; i++) {15            freqs[i] = new HashMap<>();16        }17        for (int i = 0; i < n; i++) {18            int groupIdx = i % k;19            freqs[groupIdx].put(nums[i], freqs[groupIdx].getOrDefault(nums[i], 0) + 1);20            groupSizes[groupIdx]++;21        }22 23        // DP state: dp[j] = min changes for groups processed so far to have XOR sum j24        int[] dp = new int[MAXXOR];25        Arrays.fill(dp, INF);26        dp[0] = 0; // Base case: 0 groups, XOR sum 0, 0 changes27 28        for (int i = 0; i < k; i++) {29            int[] nextDp = new int[MAXXOR];30            Arrays.fill(nextDp, INF);31            // Iterate over all possible previous XOR sums32            for (int j = 0; j < MAXXOR; j++) {33                if (dp[j] == INF) continue;34                // Iterate over all possible values `v` to set for the current group `i`35                for (int v = 0; v < MAXXOR; v++) {36                    int costToChange = groupSizes[i] - freqs[i].getOrDefault(v, 0);37                    int newXor = j ^ v;38                    nextDp[newXor] = Math.min(nextDp[newXor], dp[j] + costToChange);39                }40            }41            dp = nextDp;42        }43 44        return dp[0];45    }46}

Complexity

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)`.

Trade-offs

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.

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.

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.

Walkthrough

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:

Find the minimum cost from the previous step: min_prev_dp = min(dp). This takes O(1024).
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.
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.

1import java.util.Arrays;2import java.util.HashMap;3import java.util.Map;4 5class Solution {6    public int minChanges(int[] nums, int k) {7        int n = nums.length;8        int MAXXOR = 1 << 10;9        int INF = (int) 1e9;10 11        // Step 1: Group elements and get frequencies12        Map<Integer, Integer>[] freqs = new HashMap[k];13        int[] groupSizes = new int[k];14        for (int i = 0; i < k; i++) {15            freqs[i] = new HashMap<>();16        }17        for (int i = 0; i < n; i++) {18            int groupIdx = i % k;19            freqs[groupIdx].put(nums[i], freqs[groupIdx].getOrDefault(nums[i], 0) + 1);20            groupSizes[groupIdx]++;21        }22 23        // Step 2: DP24        int[] dp = new int[MAXXOR];25        Arrays.fill(dp, INF);26        dp[0] = 0; // Base case27 28        for (int i = 0; i < k; i++) {29            // Find the minimum cost from the previous DP state30            int minPrevDp = INF;31            for (int val : dp) {32                minPrevDp = Math.min(minPrevDp, val);33            }34            if (minPrevDp == INF) continue;35 36            int[] nextDp = new int[MAXXOR];37            // Initialize with the cost of changing to a new number38            Arrays.fill(nextDp, minPrevDp + groupSizes[i]);39            40            // Iterate through existing numbers `v` in the current group `i`41            for (Map.Entry<Integer, Integer> entry : freqs[i].entrySet()) {42                int v = entry.getKey();43                int freq = entry.getValue();44                int costToChange = groupSizes[i] - freq;45 46                // Update DP states if choosing `v` is better47                for (int j = 0; j < MAXXOR; j++) {48                    if (dp[j] != INF) {49                        int newXor = j ^ v;50                        nextDp[newXor] = Math.min(nextDp[newXor], dp[j] + costToChange);51                    }52                }53            }54            dp = nextDp;55        }56 57        return dp[0];58    }59}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int minChanges(int[] nums, int k) {4    int n = 1 << 10;5    Map<Integer, Integer>[] cnt = new Map[k];6    Arrays.setAll(cnt, i->new HashMap<>());7    int[] size = new int[k];8    for (int i = 0; i < nums.length; ++i) {9      int j = i % k;10      cnt[j].merge(nums[i], 1, Integer : : sum);11      size[j]++;12    }13    int[] f = new int[n];14    final int inf = 1 << 30;15    Arrays.fill(f, inf);16    f[0] = 0;17    for (int i = 0; i < k; ++i) {18      int[] g = new int[n];19      Arrays.fill(g, min(f) + size[i]);20      for (int j = 0; j < n; ++j) {21        for (var e : cnt[i].entrySet()) {22          int v = e.getKey(), c = e.getValue();23          g[j] = Math.min(g[j], f[j ^ v] + size[i] - c);24        }25      }26      f = g;27    }28    return f[0];29  }30private31  int min(int[] arr) {32    int mi = arr[0];33    for (int v : arr) {34      mi = Math.min(mi, v);35    }36    return mi;37  }38}

1class Solution {2public:3  int minChanges(vector<int> &nums, int k) {4    int n = 1 << 10;5    unordered_map<int, int> cnt[k];6    vector<int> size(k);7    for (int i = 0; i < nums.size(); ++i) {8      cnt[i % k][nums[i]]++;9      size[i % k]++;10    }11    vector<int> f(n, 1 << 30);12    f[0] = 0;13    for (int i = 0; i < k; ++i) {14      int mi = *min_element(f.begin(), f.end());15      vector<int> g(n, mi + size[i]);16      for (int j = 0; j < n; ++j) {17        for (auto &[v, c] : cnt[i]) {18          g[j] = min(g[j], f[j ^ v] + size[i] - c);19        }20      }21      f = move(g);22    }23    return f[0];24  }25};

1class Solution:2    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]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem