Make the XOR of All Segments Equal to Zero: DP + Bit Manipulation Pattern
LeetCode Make the XOR of All Segments Equal to Zero (Problem 1787) asks: given an integer array nums and an integer k, change the minimum number of elements in nums so that the XOR of every contiguous subarray of size k equals 0.
For example, with nums = [1, 2, 0, 3, 0] and k = 2, every pair of adjacent elements must XOR to 0. That means every pair must be equal. You need to find the fewest changes to make that happen. The constraints say values can be up to 1023 (10 bits), and the array can have up to 2000 elements. Brute force is out of the question.
Why this problem matters
This is one of the rare LeetCode problems that requires you to combine two different skill sets in a non-obvious way: XOR properties and dynamic programming. Most DP problems give you a clear state space from the start. Here, you first need to derive the state space from a mathematical property of XOR, and only then does the DP formulation emerge.
The XOR periodicity insight (that positions sharing the same index mod k must hold the same value) transforms a seemingly impossible constraint into a structured optimization. You go from "every segment must XOR to 0" to "pick k values whose XOR is 0, minimizing total changes." That transformation is the hard part. Once you see it, the DP is a well-known pattern.
This problem also teaches an important optimization technique. When your DP transition involves iterating over all possible values in a group, you can use a global minimum to handle the "non-frequent" values in bulk, reducing what would be an expensive inner loop to a manageable computation.
The key insight
If the XOR of every contiguous segment of length k is 0, consider two adjacent segments: nums[i..i+k-1] and nums[i+1..i+k]. Both XOR to 0. XOR the two equations together, and all the shared elements (nums[i+1] through nums[i+k-1]) cancel out. You are left with nums[i] XOR nums[i+k] = 0, which means nums[i] = nums[i+k].
This holds for every valid i. So positions repeat with period k. Position 0, position k, position 2k, and so on must all have the same value. Positions 1, k+1, 2k+1 must all share a value. In general, all indices with the same value of index mod k belong to the same group, and every element within a group must be identical.
Now the problem becomes: assign a value to each of the k groups such that the XOR of all k assigned values equals 0, and the total number of elements that need to change (elements that do not already match their group's assigned value) is minimized.
For each group, you can count how often each value already appears. Picking the most frequent value means fewer changes. But you cannot pick group values independently, because the k values must XOR to 0. This is where DP enters the picture.
The solution
def min_changes(nums, k):
n = len(nums)
max_val = 1024
groups = [[] for _ in range(k)]
for i in range(n):
groups[i % k].append(nums[i])
dp = [n] * max_val
dp[0] = 0
for g in range(k):
size = len(groups[g])
freq = {}
for v in groups[g]:
freq[v] = freq.get(v, 0) + 1
global_min = min(dp)
new_dp = [global_min + size] * max_val
for x in range(max_val):
if dp[x] >= n:
continue
for v, cnt in freq.items():
cost = dp[x] + size - cnt
if cost < new_dp[x ^ v]:
new_dp[x ^ v] = cost
dp = new_dp
return dp[0]
The outer loop processes each of the k groups. For each group, we build a frequency map of values currently present. The DP array dp[x] represents the minimum number of changes needed so that the cumulative XOR of all assigned group values so far equals x.
For each group, we start the new DP with the "worst case" transition: assign a value that does not appear in the group at all, costing size changes. The best we can do for an arbitrary XOR target is global_min + size, since global_min is the cheapest way to reach any previous state.
Then, for each value v that actually appears in the group (with frequency cnt), assigning v costs only size - cnt changes. We iterate through existing DP states and check if using v yields a cheaper path to new_dp[x ^ v].
The key optimization is the global minimum trick. Instead of iterating over all 1024 possible values for every DP state (which would be O(k * 1024^2)), you initialize new_dp with global_min + size. This handles every value not present in the group in O(1). You only explicitly loop over values that appear in the group, which number at most n/k. This brings the total time down to O(n + k * 1024).
Visual walkthrough
1XOR periodicity: nums[i] must equal nums[i + k]
If XOR of every k-length segment is 0, then adjacent segments share k-1 elements. Their XOR difference is nums[i] XOR nums[i+k] = 0, meaning nums[i] = nums[i+k].
2Group positions by index mod k
All positions in the same group must hold the same value. For nums = [1,2,0,3,0] with k=2: Group 0 has indices {0,2,4} with values {1,0,0}. Group 1 has indices {1,3} with values {2,3}.
3DP over groups: track XOR state after assigning each group
dp[xor_val] = minimum changes to achieve that cumulative XOR after processing groups so far. For each group, try every possible value assignment and update the DP. Values 0..1023 since nums[i] is at most 1023.
4Answer: dp[0] after all groups processed
After processing every group, dp[0] holds the minimum total changes needed so that the XOR across all k groups equals 0, which guarantees every k-length segment XORs to 0.
The walkthrough shows how the problem unfolds in four stages. First, you derive that the array must be periodic with period k. Second, you group positions by index mod k and count frequencies. Third, you run the DP, processing one group at a time, tracking the cumulative XOR and minimizing changes. Fourth, you read the answer from dp[0], because a cumulative XOR of 0 across all groups means every segment XORs to 0.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Grouped DP | O(n + k * 2^m) | O(2^m) |
Here m is the number of bits needed to represent values in the array. Since nums[i] can be at most 1023, m = 10 and 2^m = 1024. The term k * 2^m comes from the DP transitions: for each of the k groups, we iterate over all 1024 XOR states. The n term covers building frequency maps. Space is O(1024) for the DP array.
The global minimum optimization is what makes this feasible. Without it, each group would require iterating 1024 states times 1024 possible values, giving O(k * 1024^2) which is too slow for the given constraints.
The building blocks
1. XOR periodicity property
When every segment of length k XORs to 0, adjacent segments overlap in k - 1 elements. XOR-ing two adjacent segment equations cancels the overlap, leaving nums[i] = nums[i + k]. This telescoping argument is the same reasoning used in problems involving sliding window XOR constraints. Recognizing that XOR constraints create periodicity is a reusable insight.
2. Grouped frequency DP
Once you know each group of positions must share a value, the problem becomes: pick k values with XOR equal to 0, minimizing the number of elements that differ from their group's chosen value. This is a DP over a bitwise target, similar to problems like Partition Equal Subset Sum where you track a running sum. Here, instead of a running sum, you track a running XOR. The frequency map per group tells you the cost of each choice, and the global minimum trick keeps transitions efficient.
Edge cases
k equals 1. Every element is its own segment. A single element always XORs to itself, so every element must be 0. The answer is the count of non-zero elements.
All elements already satisfy the constraint. If the array is already periodic with period k and the XOR of one full period is 0, no changes are needed. The DP naturally returns 0.
k equals n. There is only one segment: the entire array. You need to make the XOR of all elements equal to 0. Each "group" has exactly one element. The DP picks one value per group to minimize changes while ensuring the total XOR is 0.
All elements are the same. If every element is v and k is even, the XOR of any segment is 0 (since v XOR v = 0 for pairs). If k is odd, you need v = 0 for the XOR to be 0. The DP handles both cases correctly through frequency counting.
From understanding to recall
The hard part of this problem is not the code. It is the derivation. You need to see that XOR constraints on overlapping segments force periodicity, then translate that into a group-based DP. In an interview, the derivation has to come quickly, or you will run out of time.
Spaced repetition helps you internalize the two-step pattern: (1) derive structural constraints from the XOR property, (2) formulate a DP over XOR states with frequency-based costs. The first few times you practice, the periodicity argument will feel unfamiliar. After a few repetitions, it becomes automatic. You see "every segment of length k must XOR to 0" and immediately think "periodic with period k, group by index mod k, DP over XOR."
Related posts
- Single Number - The foundational XOR cancellation problem
- Counting Bits - Bit manipulation combined with DP
- Partition Equal Subset Sum - DP over a target value space
These problems each exercise one of the building blocks that come together in this harder problem. Single Number teaches XOR cancellation. Counting Bits combines bits with DP. Partition Equal Subset Sum shows DP over a numeric target. Make the XOR of All Segments Equal to Zero fuses all three ideas into a single solution.