Make the XOR of All Segments Equal to Zero

Hard
1623.

Make the XOR of All Segments Equal to Zero

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.

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 <= 2000
  • 0 <= nums[i] < 2^10
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minChanges = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 2000
  • 0 <= nums[i] < 2^10

Hints for Make the XOR of All Segments Equal to Zero

  1. Hint 1

    Two consecutive windows of length k share k - 1 elements, so their XORs being equal forces nums[i] == nums[i + k]. In the final array, every position with the same i % k holds the same value.

  2. Hint 2

    So the task is: pick one value per residue class 0..k-1 so the k values XOR to 0, paying for every element of the class that differs from the picked value. Process the classes one by one with dp[x] = cheapest cost so far with running XOR x.

  3. Hint 3

    For a class of size sz, either pick a value that already occurs freq[v] times there (cost sz - freq[v], from dp[x ^ v]), or pick something absent (cost sz, from the best dp of 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

  1. Let B be the smallest power of two above max(nums) (at most 1024); every useful value lies below B.
  2. Start with dp[0] = 0 and dp[x] = ∞ otherwise.
  3. For each class g = 0..k-1, count freq[v] of its elements and its size sz. Set low = min(dp).
  4. 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 of v.
  5. 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 v for every class costs O(k * B^2); only values that actually occur need their own transition.
  • The low + sz option is essential: the best choice for a class is sometimes a value that never appears in it.
  • When k == n each 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