Make the XOR of All Segments Equal to Zero — Solution
Make the XOR of All Segments Equal to Zero solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Make the XOR of All Segments Equal to Zero is a hard coding problem on arrays, dynamic programming and bit manipulation, asked in Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Bit Manipulation
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums and an integer k. The XOR of a segment [left, right] (with left <= right) is nums[left] XOR nums[left + 1] XOR ... XOR nums[right].
In one change you may replace any element with any non-negative integer. Return the minimum number of elements to change so that every segment of length exactly k has XOR equal to 0.
Example 1
Input: nums = [1,2,0,3,0], k = 1
Output: 3
Explanation: Each single element must be 0, so the three non-zero elements change: [0,0,0,0,0].
Example 2
Input: nums = [3,4,5,2,1,7,3,4,7], k = 3
Output: 3
Explanation: Change it to [3,4,7,3,4,7,3,4,7]: every window of three is 3 XOR 4 XOR 7 = 0.
Example 3
Input: nums = [1,2,4,1,2,5,1,2,6], k = 3
Output: 3
Explanation: Change it to [1,2,3,1,2,3,1,2,3].
Constraints
1 <= k <= nums.length <= 20000 <= nums[i] < 2^10
Hints for Make the XOR of All Segments Equal to Zero
Hint 1
Two consecutive windows of length
ksharek - 1elements, so their XORs being equal forcesnums[i] == nums[i + k]. In the final array, every position with the samei % kholds the same value.Hint 2
So the task is: pick one value per residue class
0..k-1so thekvalues XOR to 0, paying for every element of the class that differs from the picked value. Process the classes one by one withdp[x]= cheapest cost so far with running XORx.Hint 3
For a class of size
sz, either pick a value that already occursfreq[v]times there (costsz - freq[v], fromdp[x ^ v]), or pick something absent (costsz, from the bestdpof all) — only the present values need individual transitions.
How to solve Make the XOR of All Segments Equal to Zero
All windows of length k XOR to zero exactly when the array is periodic with period k and one period XORs to zero. That reduces the problem to choosing one value per residue class, a DP over the running XOR of the chosen values.
Approach
- Let
Bbe the smallest power of two abovemax(nums)(at most 1024); every useful value lies belowB. - Start with
dp[0] = 0anddp[x] = ∞otherwise. - For each class
g = 0..k-1, countfreq[v]of its elements and its sizesz. Setlow = min(dp). - New
dp[x] = min(low + sz, min over present v of dp[x ^ v] + sz - freq[v]): the first term picks a value absent from the class (all its elements change; that value can make the XOR anything), the second keeps the copies ofv. - After all classes, the answer is
dp[0].
Why it works
If every window XORs to 0, then subtracting window i from window i + 1 gives nums[i] = nums[i + k], and the first window XORing to 0 covers the rest. A class's cost depends only on the chosen value. A value not in the class always costs sz, so among absent values only the cheapest predecessor matters, which is low. Restricting values below B is safe because clearing the higher bits of every chosen value keeps the XOR zero and changes no element that already matched.
Complexity
- Time —
O(B * (k + n)) with B ≤ 1024 - Space —
O(B)
Pitfalls
- Trying every value
vfor every class costsO(k * B^2); only values that actually occur need their own transition. - The
low + szoption is essential: the best choice for a class is sometimes a value that never appears in it. - When
k == neach class has one element, and the answer is 0 or 1 depending on whether the whole array already XORs to 0.
Reference solution
Python
from typing import List
def minChanges(nums: List[int], k: int) -> int:
n = len(nums)
B = 1
while B <= max(nums):
B <<= 1
INF = float('inf')
dp = [INF] * B
dp[0] = 0
for g in range(k):
freq = {}
sz = 0
for i in range(g, n, k):
freq[nums[i]] = freq.get(nums[i], 0) + 1
sz += 1
low = min(dp) + sz
items = list(freq.items())
nd = [low] * B
for x in range(B):
best = low
for v, f in items:
c = dp[x ^ v] + sz - f
if c < best:
best = c
nd[x] = best
dp = nd
return dp[0]Java
public static int minChanges(int[] nums, int k) {
int n = nums.length, mx = 0;
for (int v : nums) mx = Math.max(mx, v);
int B = 1;
while (B <= mx) B <<= 1;
final int INF = 1 << 29;
int[] dp = new int[B], freq = new int[B], vals = new int[n];
Arrays.fill(dp, INF);
dp[0] = 0;
for (int g = 0; g < k; g++) {
int cnt = 0, sz = 0;
for (int i = g; i < n; i += k) {
if (freq[nums[i]] == 0) vals[cnt++] = nums[i];
freq[nums[i]]++;
sz++;
}
int low = INF;
for (int x = 0; x < B; x++) low = Math.min(low, dp[x]);
int[] nd = new int[B];
for (int x = 0; x < B; x++) {
int best = low + sz;
for (int t = 0; t < cnt; t++) best = Math.min(best, dp[x ^ vals[t]] + sz - freq[vals[t]]);
nd[x] = best;
}
for (int t = 0; t < cnt; t++) freq[vals[t]] = 0;
dp = nd;
}
return dp[0];
}C++
int minChanges(vector<int>& nums, int k) {
int n = nums.size(), mx = 0;
for (int v : nums) mx = max(mx, v);
int B = 1;
while (B <= mx) B <<= 1;
const int INF = 1 << 29;
vector<int> dp(B, INF), freq(B, 0);
dp[0] = 0;
for (int g = 0; g < k; g++) {
vector<int> vals;
int sz = 0;
for (int i = g; i < n; i += k) {
if (freq[nums[i]] == 0) vals.push_back(nums[i]);
freq[nums[i]]++;
sz++;
}
int low = *min_element(dp.begin(), dp.end());
vector<int> nd(B);
for (int x = 0; x < B; x++) {
int best = low + sz;
for (int v : vals) best = min(best, dp[x ^ v] + sz - freq[v]);
nd[x] = best;
}
for (int v : vals) freq[v] = 0;
dp = nd;
}
return dp[0];
}JavaScript
var minChanges = function(nums, k) {
var n = nums.length, mx = 0;
for (var i = 0; i < n; i++) if (nums[i] > mx) mx = nums[i];
var B = 1;
while (B <= mx) B <<= 1;
var INF = 1 << 29, dp = new Array(B).fill(INF), freq = new Array(B).fill(0);
dp[0] = 0;
for (var g = 0; g < k; g++) {
var vals = [], sz = 0;
for (var i = g; i < n; i += k) {
if (freq[nums[i]] === 0) vals.push(nums[i]);
freq[nums[i]]++;
sz++;
}
var low = INF;
for (var x = 0; x < B; x++) if (dp[x] < low) low = dp[x];
var nd = new Array(B);
for (var x = 0; x < B; x++) {
var best = low + sz;
for (var t = 0; t < vals.length; t++) {
var c = dp[x ^ vals[t]] + sz - freq[vals[t]];
if (c < best) best = c;
}
nd[x] = best;
}
for (var t = 0; t < vals.length; t++) freq[vals[t]] = 0;
dp = nd;
}
return dp[0];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming