#1787

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Make the XOR of All Segments Equal to Zero

Determine the minimum changes needed in an array so all size-k segments XOR to zero using DP and bit manipulation.

array dynamic programming bit manipulation

Problem Statement

Given an array nums and an integer k, the XOR of a segment [left, right] is defined as nums[left] XOR nums[left+1] XOR ... XOR nums[right]. Determine the minimum number of elements you must change so that every contiguous segment of size k has an XOR equal to zero.

For example, if nums = [1,2,0,3,0] and k = 1, changing elements to [0,0,0,0,0] yields all segments XORing to zero. You must implement an algorithm to find this minimal number of changes for any valid array and k, optimizing using state transition dynamic programming.

Examples

Example 1

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

Output: 3

Modify the array from [1,2,0,3,0] to from [0,0,0,0,0].

Example 2

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

Output: 3

Modify the array from [3,4,5,2,1,7,3,4,7] to [3,4,7,3,4,7,3,4,7].

Example 3

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

Output: 3

Modify the array from [1,2,4,1,2,5,1,2,6] to [1,2,3,1,2,3,1,2,3].

Constraints

1 <= k <= nums.length <= 2000
0 <= nums[i] < 210

Solution Approach

Identify independent position groups

Segmenting positions modulo k allows each group to be treated independently because nums[i] must equal nums[i+k] to satisfy the XOR constraint across all segments. This reduces the problem to adjusting each group with minimal changes.

Apply state transition dynamic programming

For each group, maintain a DP array mapping XOR values to minimum changes. Transition by considering all values in the group, updating the DP to reflect either keeping or changing the element to achieve a target XOR. This efficiently propagates optimal solutions across groups.

Aggregate minimal changes across all groups

After processing each group, combine results to find the overall minimum number of element modifications. The final answer is the sum of minimal changes for all independent groups, guaranteeing all size-k segments XOR to zero.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * 2^m) where n is the array length and m is the max bit width of nums elements, due to DP over XOR states for each position group. Space complexity is O(2^m * k) for storing DP tables per group.

What Interviewers Usually Probe

Notice the repeating pattern every k elements; this hints at grouping indices modulo k.
Consider dynamic programming over XOR states; naive brute-force leads to timeouts.
Pay attention to bit width of elements; optimizing DP for feasible states is key.

Common Pitfalls or Variants

Common pitfalls

Ignoring the modulo k grouping causes redundant computation and incorrect minimal changes.
Not tracking XOR transitions correctly can lead to overcounting changes.
Assuming segments are independent without considering overlapping indices breaks correctness.

Follow-up variants

Compute minimal changes for segments of varying lengths instead of fixed k.
Find the number of ways to modify the array to satisfy XOR zero per segment.
Extend the problem to 2D grids where XOR of subgrids must be zero.

FAQ

What is the main pattern to solve Make the XOR of All Segments Equal to Zero?

The key pattern is state transition dynamic programming over position groups modulo k, using XOR state tracking to minimize changes.

Why do we group array indices modulo k?

Grouping indices modulo k isolates independent sequences, since nums[i] must match nums[i+k] to satisfy all segments XORing to zero.

Can we solve this problem without bit manipulation?

Bit manipulation is crucial for efficiently handling XOR states; without it, the DP approach becomes infeasible for larger numbers.

What is the time complexity of this approach?

Time complexity is roughly O(n * 2^m) where n is array length and m is bit width of elements, due to DP over XOR states per group.

How do overlapping segments affect the solution?

Overlapping segments mean a change affects multiple segments; handling this through grouped DP ensures the minimal total changes are counted correctly.

terminal

Solution

Solution 1: Dynamic Programming

Notice that after modifying the array `nums`, the XOR result of any interval of length $k$ is equal to $0$. Therefore, for any $i$, we have:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def minChanges(self, nums: List[int], k: int) -> int:
        n = 1 << 10
        cnt = [Counter() for _ in range(k)]
        size = [0] * k
        for i, v in enumerate(nums):
            cnt[i % k][v] += 1
            size[i % k] += 1
        f = [inf] * n
        f[0] = 0
        for i in range(k):
            g = [min(f) + size[i]] * n
            for j in range(n):
                for v, c in cnt[i].items():
                    g[j] = min(g[j], f[j ^ v] + size[i] - c)
            f = g
        return f[0]

Continue Practicing

#1799 maximize score after n operations #1815 maximum number of groups getting fresh donuts #1755 closest subsequence sum