[LeetCode] Make the XOR of All Segments Equal to Zero

1787. Make the XOR of All Segments Equal to Zero

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.

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
#define INF 987654321
class Solution {
int dp[2000][2000];
int helper(vector<int>& S, vector<unordered_map<int,int>>& F, int p, int x) {
if(p == S.size()) return x ? INF : 0;
if(dp[p][x] != -1) return dp[p][x];
int& res = dp[p][x] = INF;
for(auto& [n, f] : F[p]) {
res = min(res,
S[p] - f + helper(S,F,p+1,n^x)
);
}
return res;
}
public:
int minChanges(vector<int>& A, int k) {
memset(dp, -1, sizeof dp);
vector<int> sum(k), best(k);
vector<unordered_map<int,int>> freq(k);
int n = A.size(), change = 0;
for(int i = 0; i < n; i++) {
sum[i % k]++;
best[i % k] = max(best[i % k], ++freq[i % k][A[i]]);
}

for(int i = 0; i < k; i++) {
change += sum[i] - best[i];
}

int res = helper(sum, freq, 0, 0);
for(int i = 0; i < k; i++) {
res = min(res, change + best[i]);
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/04/27/PS/LeetCode/make-the-xor-of-all-segments-equal-to-zero/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.