Make the XOR of All Segments Equal to Zero

Make the XOR of All Segments Equal to Zero - Problem

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.

A segment of size k starting at position i includes elements nums[i], nums[i+1], ..., nums[i+k-1].

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,0,3,1], k = 3

› Output: 3

💡 Note: We need segments [1,2,0], [2,0,3], [0,3,1] to all XOR to 0. One solution: change nums to [0,0,0,0,0], requiring 3 changes (positions 0,1,3).

Example 2 — Smaller Array

$ Input: nums = [3,4,5,2], k = 2

› Output: 2

💡 Note: Segments are [3,4], [4,5], [5,2]. Need 3⊕4=0, 4⊕5=0, 5⊕2=0. Change to [0,0,1,1]: segments become [0,0], [0,1], [1,1] - but this doesn't work. Better: change to [1,1,1,1] - 2 changes.

Example 3 — Minimum Size

$ Input: nums = [1,2], k = 2

› Output: 1

💡 Note: Only one segment [1,2]. Need 1⊕2=3 to become 0. Change one element: [0,0] gives 0⊕0=0. Cost: 1 change.

Constraints

1 ≤ nums.length ≤ 2000
1 ≤ k ≤ nums.length
0 ≤ nums[i] < 2¹⁰

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with segments of size k that overlap

Segments XOR

Each k-length segment must XOR to zero

Minimum Changes

Find minimum elements to change

Key Takeaway

🎯 Key Insight: Elements at positions with same remainder mod k are related across all segments

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that positions with the same remainder when divided by k must have related values across all segments. The optimal approach uses dynamic programming to group positions and find minimum-cost assignments that make all segments XOR to zero. Time: O(n × 1024), Space: O(k × 1024)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Backtracking	O(1024^n)	O(n)	Try all possible value assignments and count minimum changes
Dynamic Programming with Position Groups	O(n × 1024)	O(k × 1024)	Group positions by remainder mod k and use DP to find optimal assignments
Optimized Greedy with Pattern Recognition	O(n)	O(k + unique_values)	Use greedy strategy based on frequency analysis within position groups

Brute Force with Backtracking — Algorithm Steps

Try each possible value for each position
Check if all k-segments XOR to zero
Backtrack and try next combination
Return minimum changes found

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Values

For each position, try all possible values 0-1023

Check Segments

Verify all k-length segments XOR to zero

Backtrack

Return minimum changes across all combinations

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int backtrack(int* nums, int n, int k, int pos, int changes) {
    if (pos == n) {
        // Check all segments
        for (int i = 0; i <= n - k; i++) {
            int xorSum = 0;
            for (int j = i; j < i + k; j++) {
                xorSum ^= nums[j];
            }
            if (xorSum != 0) return INT_MAX;
        }
        return changes;
    }
    
    // Try keeping current value
    int result = backtrack(nums, n, k, pos + 1, changes);
    
    // Try changing to different values
    int original = nums[pos];
    for (int val = 0; val < 1024; val++) {
        if (val != original) {
            nums[pos] = val;
            int newResult = backtrack(nums, n, k, pos + 1, changes + 1);
            if (newResult < result) result = newResult;
        }
    }
    nums[pos] = original;
    
    return result;
}

int solution(int* nums, int n, int k) {
    if (n < k) return 0;
    return backtrack(nums, n, k, 0, 0);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    int nums[1000], n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    int k;
    scanf("%d", &k);
    printf("%d\n", solution(nums, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1024^n)

For each of n positions, try up to 1024 possible values

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth up to n levels

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~35 min Avg. Time

427 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler