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 <= 20000 <= nums[i] < 210
Solutions#
Solution 1#
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]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public int minChanges(int[] nums, int k) {
int n = 1 << 10;
Map<Integer, Integer>[] cnt = new Map[k];
Arrays.setAll(cnt, i -> new HashMap<>());
int[] size = new int[k];
for (int i = 0; i < nums.length; ++i) {
int j = i % k;
cnt[j].merge(nums[i], 1, Integer::sum);
size[j]++;
}
int[] f = new int[n];
final int inf = 1 << 30;
Arrays.fill(f, inf);
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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
int minChanges(vector<int>& nums, int k) {
int n = 1 << 10;
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, 1 << 30);
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];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| 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 := slices.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]
}
|
