Formatted question description: https://leetcode.ca/all/1787.html

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

Hard

## Description

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.

Example 1:

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

Output: 3

Explanation: 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

Explanation: 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

Explanation: 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] < 2^10

## Solution

Divide the elements in nums into k groups, where all the elements in the same group have indices with the same remainder when divided by k.

Create a 2D array dp with k + 1 rows and 1 << 10 columns, where dp[i][j] represents the minimum number of elements to change for the i-th group to make XOR value equal to j. For i = 0, there is dp = 0 and dp[j] = INF when j > 0.

For 0 <= i < k, initialize dp[i + 1] with min(dp[i]) + size[i]. For 0 <= j < 1 << 10, if dp[i][j] != INF, update the values in dp[i + 1]. For val' in the i + 1-th group, enumerate previous val in the i-th group, and update dp[i + 1][val ^ val'] accordingly.

Finally, return dp[k].

class Solution {
public int minChanges(int[] nums, int k) {
final int INF = 0x3f3f3f3f;
final int MAX = 1 << 10;
int length = nums.length;
Map<Integer, Integer>[] groups = new Map[k];
for (int i = 0; i < k; i++)
groups[i] = new HashMap<Integer, Integer>();
int[] size = new int[k];
for (int i = 0; i < k; i++) {
for (int j = i; j < length; j += k) {
groups[i].put(nums[j], groups[i].getOrDefault(nums[j], 0) + 1);
size[i]++;
}
}
int[][] dp = new int[k + 1][MAX];
Arrays.fill(dp, INF);
dp = 0;
for (int i = 0; i < k; i++) {
int low = Arrays.stream(dp[i]).min().getAsInt();
Arrays.fill(dp[i + 1], low + size[i]);
for (int j = 0; j < MAX; j++) {
if (dp[i][j] != INF) {
for (Map.Entry<Integer, Integer> entry : groups[i].entrySet()) {
int key = entry.getKey(), value = entry.getValue();
int next = key ^ j;
dp[i + 1][next] = Math.min(dp[i + 1][next], dp[i][j] + size[i] - value);
}
}
}
}
return dp[k];
}
}