Make the XOR of All Segments Equal to Zero
HardPrompt
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] < 210
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 zeroimplies thatnums[i] = nums[i+k]for all0 <= i < n-k. This means the array must be periodic with periodk. - This property partitions the array indices into
kgroups based onindex % 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 satisfyv_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 firstigroups (from group 0 toi-1) such that the XOR sum of their chosen values isj. - State:
dp[i][j]= minimum changes for groups0, ..., i-1to have an XOR sum ofj. - Initialization:
dp[0][0] = 0, anddp[0][j] = infinityforj > 0. - Transition: To compute
dp[i][j], we iterate through all possible valuesv(from 0 to 1023) for groupi-1. If we choosevfor groupi-1, the XOR sum of the firsti-1groups must have beenj ^ v. The cost for changing groupi-1tovissize_{i-1} - freq_{i-1}[v], wheresize_{i-1}is the number of elements in the group andfreq_{i-1}[v]is the frequency ofvin 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
kgroups to have an XOR sum of 0 isdp[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.
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]; }}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.
Solutions
Solution
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; }}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.