Difficulty: 🔴 Hard
Topics: Array, Hash Table, Dynamic Programming, Bit Manipulation, Counting

Solution

LeetCode 1787. Make the XOR of All Segments Equal to Zero

Problem Understanding

We are given an array nums and an integer k. Every contiguous segment of length k must have XOR equal to 0 after we perform some modifications to the array. Our goal is to change as few elements as possible.

For a segment of length k, the XOR is:

nums[i] XOR nums[i+1] XOR ... XOR nums[i+k-1]

The requirement is that every such segment must evaluate to zero.

The output is the minimum number of positions whose values need to be changed so that this condition holds.

The constraints are important:

1 <= k <= nums.length <= 2000
0 <= nums[i] < 2^10

The second constraint is especially significant. Since every value is less than 1024, every XOR result is also in the range [0, 1023]. This means there are only 1024 possible XOR states, which strongly suggests a dynamic programming solution over XOR values.

A key observation comes from comparing consecutive length-k segments.

Suppose:

nums[i] XOR nums[i+1] XOR ... XOR nums[i+k-1] = 0
nums[i+1] XOR nums[i+2] XOR ... XOR nums[i+k] = 0

XORing these equations together cancels the shared elements:

nums[i] = nums[i+k]

Therefore, every element must equal the element k positions ahead.

This means the final array must satisfy:

nums[i] = nums[i+k] = nums[i+2k] = ...

So indices with the same remainder modulo k form a group, and every value inside a group must become identical.

The problem becomes:

Divide indices into k groups according to index % k.
Choose one final value for each group.
The XOR of the chosen values across all groups must be 0.
Minimize the number of modified elements.

Important edge cases include:

k = 1, where every element must become 0.
k = n, where there is only one segment, so only the total XOR matters.
Groups with very different sizes.
Values already satisfying the XOR condition.
Cases where choosing a value not currently present in a group is optimal.

Approaches

Brute Force

The transformed problem asks us to choose one value for each modulo group.

Each chosen value must be between 0 and 1023.

A brute force solution would try all assignments:

group0 value
group1 value
...
group(k-1) value

and check whether their XOR is zero.

Since there are 1024 possibilities per group, this requires:

1024^k

combinations.

Even for small k, this is completely infeasible.

The approach is correct because it examines every possible valid assignment, but it is far too slow.

Key Insight

Indices with the same remainder modulo k must become equal.

For each group:

Let size be the number of elements in the group.
Let freq[x] be how many times value x already appears.

If we decide the group's final value is x, then:

cost = size - freq[x]

because every element not already equal to x must be changed.

Now we only need to choose one value per group such that:

chosen0 XOR chosen1 XOR ... XOR chosen(k-1) = 0

and the total modification cost is minimized.

Since XOR values are limited to 1024 possibilities, we can use dynamic programming:

dp[x] = minimum cost after processing some groups
        with cumulative XOR equal to x

This reduces the problem to approximately:

O(k * 1024)

states, with careful optimization.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(1024^k)	O(k)	Tries every possible value assignment
Optimal DP	O(k × 1024 + n)	O(1024)	DP over XOR states using modulo groups

Algorithm Walkthrough

Step 1: Build modulo groups

For every index i, place nums[i] into group:

i % k

All elements inside the same group must eventually become identical.

Step 2: Count frequencies

For each group:

Compute its size.
Count occurrences of every value.

Example:

group = [3,3,7]

gives:

size = 3

freq:
3 -> 2
7 -> 1

Step 3: Define DP state

Let:

dp[x]

represent the minimum modification cost after processing some groups and obtaining cumulative XOR x.

Initially:

dp[0] = 0
dp[others] = infinity

because before choosing any group values, the XOR is 0.

Step 4: Process one group

Suppose the current group size is cnt.

If we change every element in this group arbitrarily, the cost is:

cnt

This gives a baseline transition.

Let:

best = min(dp)

Then every new XOR state can start with:

best + cnt

which corresponds to changing the entire group.

Step 5: Improve using existing frequencies

For each value v that already appears in the group:

cost(v) = cnt - freq[v]

If previous XOR is:

old

then choosing value v produces:

new = old XOR v

and:

newDP[new] =
    min(newDP[new],
        dp[old] + cost(v))

This captures the benefit of keeping occurrences already equal to v.

Step 6: Replace DP

After all transitions for the current group:

dp = newDP

and continue to the next group.

Step 7: Return answer

After all groups are processed, we need total XOR equal to zero:

dp[0]

which is the minimum number of modifications.

Why it works

Every valid final array must assign exactly one value to each modulo group. The cost of choosing a value depends only on the frequency distribution inside that group. The XOR constraint depends only on the chosen values. The dynamic programming state records the minimum cost for every achievable cumulative XOR after processing groups. Since every group choice is considered and all XOR states are maintained, the DP explores every valid assignment while always keeping the cheapest cost. Therefore dp[0] after the final group is the optimal answer.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def minChanges(self, nums: List[int], k: int) -> int:
        MAXX = 1024
        INF = float('inf')

        dp = [INF] * MAXX
        dp[0] = 0

        for start in range(k):
            freq = Counter()
            count = 0

            for i in range(start, len(nums), k):
                freq[nums[i]] += 1
                count += 1

            best_prev = min(dp)

            new_dp = [best_prev + count] * MAXX

            for value, occurrences in freq.items():
                keep_cost = count - occurrences

                for xor_state in range(MAXX):
                    new_dp[xor_state ^ value] = min(
                        new_dp[xor_state ^ value],
                        dp[xor_state] + keep_cost
                    )

            dp = new_dp

        return dp[0]

The implementation follows the algorithm exactly.

The array is partitioned implicitly by iterating through indices with the same remainder modulo k. For each group, a frequency table is built using Counter.

The DP array stores the minimum cost for every XOR value from 0 to 1023. Before processing a group, we compute best_prev = min(dp). This allows us to initialize every state in the next DP layer with the cost of changing the entire group.

The second transition uses only values that actually appear in the group. If a value appears f times in a group of size cnt, then selecting that value requires changing only cnt - f elements. These transitions improve the baseline DP values.

After all groups are processed, dp[0] represents the minimum cost achieving total XOR zero.

Go Solution

package main

import "math"

func minChanges(nums []int, k int) int {
	const MAXX = 1024
	const INF = math.MaxInt32 / 2

	dp := make([]int, MAXX)
	for i := 1; i < MAXX; i++ {
		dp[i] = INF
	}

	for start := 0; start < k; start++ {
		freq := make(map[int]int)
		count := 0

		for i := start; i < len(nums); i += k {
			freq[nums[i]]++
			count++
		}

		bestPrev := INF
		for _, v := range dp {
			if v < bestPrev {
				bestPrev = v
			}
		}

		newDP := make([]int, MAXX)
		for i := 0; i < MAXX; i++ {
			newDP[i] = bestPrev + count
		}

		for value, occurrences := range freq {
			keepCost := count - occurrences

			for xorState := 0; xorState < MAXX; xorState++ {
				next := xorState ^ value
				candidate := dp[xorState] + keepCost

				if candidate < newDP[next] {
					newDP[next] = candidate
				}
			}
		}

		dp = newDP
	}

	return dp[0]
}

The Go implementation mirrors the Python version closely. A map[int]int is used instead of Counter, and slices are used for DP storage. Since all costs are bounded by n ≤ 2000, standard int arithmetic is completely safe and there are no overflow concerns.

Worked Examples

Example 1

nums = [1,2,0,3,0]
k = 1

Groups:

Group	Elements
0	[1,2,0,3,0]

Frequency table:

Value	Count
0	2
1	1
2	1
3	1

Group size:

Choosing final value:

Value	Cost
0	3
1	4
2	4
3	4

To obtain XOR 0, the only group must choose value 0.

Result:

Example 2

nums = [3,4,5,2,1,7,3,4,7]
k = 3

Groups:

Group	Elements
0	[3,2,3]
1	[4,1,4]
2	[5,7,7]

Frequency tables:

Group 0:

Value	Count
3	2
2	1

Group 1:

Value	Count
4	2
1	1

Group 2:

Value	Count
7	2
5	1

Best choices:

3 XOR 4 XOR 7 = 0

Costs:

1 + 1 + 1 = 3

Result:

Example 3

nums = [1,2,4,1,2,5,1,2,6]
k = 3

Groups:

Group	Elements
0	[1,1,1]
1	[2,2,2]
2	[4,5,6]

Group costs:

Chosen Value	Cost
4	2
5	2
6	2
Other	3

Need:

1 XOR 2 XOR x = 0

Thus:

x = 3

Value 3 is not present in the group.

Cost:

Result:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k × 1024 + n + 1024 × U)	Each group processes all XOR states, where U is the number of distinct values in the group
Space	O(1024)	Two DP arrays of size 1024

Since every value is less than 1024, the XOR state space is fixed. The practical complexity is approximately:

O(k * 1024 * average_distinct_values)

which easily fits within the constraints n ≤ 2000.

Test Cases

sol = Solution()

assert sol.minChanges([1, 2, 0, 3, 0], 1) == 3      # example 1
assert sol.minChanges([3,4,5,2,1,7,3,4,7], 3) == 3 # example 2
assert sol.minChanges([1,2,4,1,2,5,1,2,6], 3) == 3 # example 3

assert sol.minChanges([0], 1) == 0                 # single element already valid
assert sol.minChanges([5], 1) == 1                 # single element must become 0

assert sol.minChanges([1,1,1,1], 2) == 2           # repeated values, xor mismatch
assert sol.minChanges([0,0,0,0], 2) == 0           # already valid

assert sol.minChanges([1,2,3], 3) == 0             # total xor already zero
assert sol.minChanges([1,2,4], 3) == 1             # one change fixes xor

assert sol.minChanges([7,7,7,7,7,7], 3) == 2       # modulo groups interact

assert sol.minChanges([1,2,1,2,1,2], 2) == 0       # already periodic

assert sol.minChanges([1,1,1,2,2,2], 3) == 2       # requires changing one group

assert sol.minChanges([1023,1023,1023], 1) == 3    # maximum value range

Test Summary

Test	Why
`[1,2,0,3,0], k=1`	Official example 1
`[3,4,5,2,1,7,3,4,7], k=3`	Official example 2
`[1,2,4,1,2,5,1,2,6], k=3`	Official example 3
`[0], k=1`	Smallest valid input
`[5], k=1`	Single element requiring change
`[1,1,1,1], k=2`	Repeated values with XOR conflict
`[0,0,0,0], k=2`	Already satisfies condition
`[1,2,3], k=3`	Whole array XOR already zero
`[1,2,4], k=3`	One modification needed
`[7,7,7,7,7,7], k=3`	Multiple groups with same value
`[1,2,1,2,1,2], k=2`	Already periodic structure
`[1,1,1,2,2,2], k=3`	Group interaction test
`[1023,1023,1023], k=1`	Maximum allowed value

Edge Cases

Case 1: `k = 1`

When k = 1, every segment contains exactly one element. Since every segment XOR must be zero, every array element must become 0. A common mistake is to apply the general logic without noticing this simplification. The DP handles it naturally because there is only one group containing all elements, and the minimum cost is exactly the number of nonzero entries.

Case 2: Choosing a Value Not Present in a Group

Many greedy attempts only consider values already appearing in a group. This is incorrect. Sometimes the XOR constraint forces a group to adopt a completely new value. Example 3 demonstrates this, where the optimal choice is value 3, which does not appear in the third group. The DP correctly handles this through the baseline transition best + count, representing changing the entire group to any arbitrary value.

Case 3: `k = n`

When k equals the array length, there is only one segment. The requirement reduces to making the XOR of the entire array equal to zero. The modulo grouping creates n groups of size one. The DP still works correctly because each group contributes one chosen value, and the final XOR constraint remains exactly the same.

Case 4: Highly Uneven Frequency Distributions

A group may contain one value many times and several other values rarely. Greedy strategies that always keep the majority value can fail because the global XOR constraint couples all groups together. The DP keeps every XOR possibility and therefore never commits too early to a locally optimal choice.

Case 5: Already Valid Arrays

Some inputs already satisfy the condition. A buggy implementation might force unnecessary changes. Since the DP starts with dp[0] = 0 and always tracks minimum costs, it preserves the zero-cost solution whenever the existing group assignments already produce cumulative XOR zero.

LeetCode 1787 - Make the XOR of All Segments Equal to Zero

Solution

LeetCode 1787. Make the XOR of All Segments Equal to Zero

Problem Understanding

Approaches

Brute Force

Key Insight

Approach Comparison

Algorithm Walkthrough

Step 1: Build modulo groups

Step 2: Count frequencies

Step 3: Define DP state

Step 4: Process one group

Step 5: Improve using existing frequencies

Step 6: Replace DP

Step 7: Return answer

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Example 2

Example 3

Complexity Analysis

Test Cases

Test Summary

Edge Cases

Case 1: k = 1

Case 2: Choosing a Value Not Present in a Group

Case 3: k = n

Case 4: Highly Uneven Frequency Distributions

Case 5: Already Valid Arrays

Case 1: `k = 1`

Case 3: `k = n`