##### Welcome to Subscribe On Youtube

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][0] = 0 and dp[0][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][0].

• 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[0], INF);
dp[0][0] = 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][0];
}
}

############

class Solution {
public int minChanges(int[] nums, int k) {
int n = 1 << 10;
Map<Integer, Integer>[] cnt = new Map[k];
int[] size = new int[k];
for (int i = 0; i < k; ++i) {
cnt[i] = new HashMap<>();
}
for (int i = 0; i < nums.length; ++i) {
cnt[i % k].put(nums[i], cnt[i % k].getOrDefault(nums[i], 0) + 1);
size[i % k]++;
}
int[] f = new int[n];
Arrays.fill(f, 0x3f3f3f3f);
f[0] = 0;
for (int i = 0; i < k; ++i) {
int[] g = new int[n];
Arrays.fill(g, min(f) + size[i]);
for (int j = 0; j < n; ++j) {
for (var e : cnt[i].entrySet()) {
int v = e.getKey(), c = e.getValue();
g[j] = Math.min(g[j], f[j ^ v] + size[i] - c);
}
}
f = g;
}
return f[0];
}

private int min(int[] arr) {
int mi = arr[0];
for (int v : arr) {
mi = Math.min(mi, v);
}
return mi;
}
}

• 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]


• class Solution {
public:
int minChanges(vector<int>& nums, int k) {
int n = 1 << 10;
vector<unordered_map<int, int>> cnt(k);
vector<int> size(k);
for (int i = 0; i < nums.size(); ++i) {
cnt[i % k][nums[i]]++;
size[i % k]++;
}
vector<int> f(n, 0x3f3f3f3f);
f[0] = 0;
for (int i = 0; i < k; ++i) {
int mi = *min_element(f.begin(), f.end());
vector<int> g(n, mi + size[i]);
for (int j = 0; j < n; ++j) {
for (auto& [v, c] : cnt[i]) {
g[j] = min(g[j], f[j ^ v] + size[i] - c);
}
}
f = move(g);
}
return f[0];
}
};

• func minChanges(nums []int, k int) int {
n := 1 << 10
cnt := make([]map[int]int, k)
for i := range cnt {
cnt[i] = map[int]int{}
}
size := make([]int, k)
for i, v := range nums {
cnt[i%k][v]++
size[i%k]++
}
f := make([]int, n)
for i := 1; i < n; i++ {
f[i] = 0x3f3f3f3f
}
for i, sz := range size {
g := make([]int, n)
x := min(f...) + sz
for i := range g {
g[i] = x
}
for j := 0; j < n; j++ {
for v, c := range cnt[i] {
g[j] = min(g[j], f[j^v]+sz-c)
}
}
f = g
}
return f[0]
}

func min(a ...int) int {
mi := a[0]
for _, v := range a {
if mi > v {
mi = v
}
}
return mi
}