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.

c++

#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;
    }
};