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

DP

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:

English Version in Youtube

中文版解答Youtube Link

中文版解答Bilibili Link

class Solution {
public:
    int minChanges(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<int>> freq(k, vector<int>(1025, 0));
        for (int i = 0; i < n; i++) {
            freq[i%k][nums[i]]++;
        }
        
        vector<vector<int>> dp(k + 1, vector<int>(1025, 2001));
        dp[0][0] = 0;
        
        for (int i = 0; i < k; i++) {
            int total = (n + k - i - 1) / k;
            int previous_minimum_changes = *min_element(dp[i].begin(), dp[i].end());
            
            for (int target = 0; target <= 1024; target++) {
                dp[i+1][target] = total + previous_minimum_changes;
                
                for (int index = i; index < n; index += k) {
                    int picked = nums[index];
                    int previous_target = picked ^ target;
                    if (previous_target > 1024) {
                        continue;
                    }
                    dp[i+1][target] = min(dp[i+1][target],
                                          dp[i][previous_target] + total - freq[i][picked]);
                }
            }
        }
        
        return dp[k][0];
    }
};