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 <= 20000 <= nums[i] < 210Problem Overview: You are given an array nums and an integer k. Every contiguous segment of length k must have XOR equal to 0. You can change any element. The goal is to minimize the number of modifications.
Approach 1: Greedy Frequency Selection (Approximate Greedy) (Time: O(n + k * 1024), Space: O(1024))
Observe that elements contributing to the same segment positions repeat every k indices. Group elements by i % k. Each group affects the XOR of every segment exactly once. A greedy idea is to replace values in each group with the most frequent value in that group, minimizing local changes. Track frequencies using hash maps or fixed arrays since values are within a small bit range.
The limitation is that independent greedy choices might not produce a global XOR of zero across groups. You still compute the XOR of chosen representatives and may need extra adjustments. This method is useful for building intuition about the repeating structure of the problem and why group-based reasoning works.
Approach 2: Dynamic Programming over XOR States (Optimal) (Time: O(n + k * 1024), Space: O(1024))
Split the array into k groups by index modulo k. For each group, count the frequency of every value. Since numbers are < 2^10, there are only 1024 possible XOR states. Define dp[x] as the minimum changes needed so processed groups produce XOR x.
For each group, try assigning a value v. The cost equals group_size - freq[v] (number of elements you must change). Update the next DP state with new_xor = prev_xor ^ v. To avoid iterating all possibilities repeatedly, track the minimum value in the previous DP layer and use it as a fallback when assigning unseen values. This reduces the transition cost dramatically.
This technique combines array grouping, frequency counting, and state transitions typical in dynamic programming. XOR transitions rely on properties from bit manipulation. After processing all k groups, the answer is dp[0] because the final XOR must be zero.
Recommended for interviews: The dynamic programming approach is the expected solution. Interviewers want to see recognition of the i % k grouping pattern and a DP state representing XOR possibilities. The greedy reasoning helps explain the structure, but the DP solution demonstrates strong problem‑solving skills with bitwise state transitions.
This approach works by checking each segment of length k and ensuring that its XOR is zero. For each segment, calculate the XOR of the current elements. If the XOR is not zero, identify which element can be flipped to achieve the desired XOR, trying to minimize changes across overlapping segments. This greedy approach is quick but might not always be optimal due to the choice of elements flipped.
This solution iterates over the array, checking each position modulo k. It maintains a frequency dictionary for elements at positions that share the same modulo result. For each segment starting at position i % k, it calculates the XOR. If it isn't zero, it computes the changes needed to convert the XOR to zero by changing the least frequent element that brings the total XOR to zero.
The time complexity is O(n), where n is the length of the array, due to the loop iterating through the array. The space complexity is O(n/k) because it stores frequency counts for elements in one segment of size n/k.
This approach uses dynamic programming to keep track of the minimum changes necessary to ensure all segments of an array of k have an XOR equal to zero. We calculate the possible values for all segments and use a DP table to store the minimum number of changes necessary for each prefix of the array.
The DP approach initializes a state array dp where each entry represents the minimum modifications required for each XOR possibility. For each position modulo k, the algorithm considers each possible XOR value and finds the number of changes needed to achieve this XOR value using the elements in the current segment. This allows efficient updates of XOR possibilities as we progress through the array.
The time complexity is O((n/k) * (2^x)), with x being the bit length of elements in the array, due to managing XOR value possibilities for every segment. The space complexity is O(2^x) due to the DP array storing possible XOR states.
Notice that after modifying the array nums, the XOR result of any interval of length k is equal to 0. Therefore, for any i, we have:
$
nums[i] \oplus nums[i+1] \oplus ... \oplus nums[i+k-1] = 0
and
nums[i+1] \oplus nums[i+2] \oplus ... \oplus nums[i+k] = 0
Combining the two equations and the properties of XOR operation, we can get nums[i] \oplus nums[i+k] = 0, which means nums[i]=nums[i+k]. We find that the elements in the modified array knums are cyclic with a period of . The numbers congruent modulo k can only take a fixed value, and the XOR result of the first k numbers must be 0.
First, we count each group i, the number of elements in each group is size[i], and the number of elements with value v in each group is cnt[i][v].
Next, we can use dynamic programming to solve it. Let f[i][j] represent the minimum number of modifications with the XOR sum of the first i+1 groups being j. Since the value of each group is only related to the value of the previous group, we can use a rolling array to optimize the space complexity.
Redefine f[j] to represent the minimum number of modifications with the XOR sum being j when processing to the current group.
When transitioning states, there are two choices: one is to modify all the numbers in the current group to the same value, then we can choose the one with the smallest previous cost, plus the number of elements size[i] in this group, the cost is min{f[0..n]} + size[i]; the second is to modify all the numbers in the current group to some value j of the current group, enumerate j and the element v of the current group, then the previous cost is f[j \oplus v], the cost is f[j \oplus v] + size[i] - cnt[i][v]. Take the minimum value.
The final answer is f[0].
The time complexity is O(2^{C}times k + n). Where n is the length of the array Cnums, and is the maximum number of bits in the binary representation of the elements in C=10$.nums, in this problem
| Approach | Complexity |
|---|---|
| Greedy Approach | The time complexity is O(n), where n is the length of the array, due to the loop iterating through the array. The space complexity is O(n/k) because it stores frequency counts for elements in one segment of size n/k. |
| Dynamic Programming Approach | The time complexity is O((n/k) * (2^x)), with x being the bit length of elements in the array, due to managing XOR value possibilities for every segment. The space complexity is O(2^x) due to the DP array storing possible XOR states. |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Frequency Selection | O(n + k * 1024) | O(1024) | Understanding the repeating index pattern and minimizing local changes per group |
| Dynamic Programming over XOR States | O(n + k * 1024) | O(1024) | General optimal solution ensuring final XOR across groups equals zero |
LeetCode 1787. Make the XOR of All Segments Equal to Zero • Happy Coding • 2,230 views views
Watch 7 more video solutions →Practice Make the XOR of All Segments Equal to Zero with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor