1787. Make the XOR of All Segments Equal to Zero

Description

You are given an array nums​​​ and an integer k​​​​​. The 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] < 210

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(n²)
• Space complexity: O(nk)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const minChanges = function (nums, k) {
  const MAX_XOR = 1024;
  const n = nums.length;
  const counts = Array.from({ length: k }, () => new Map());
  const dp = Array.from({ length: k }, () => new Array(MAX_XOR).fill(n));

  const getGroupCount = index => Math.floor(n / k) + (n % k > index ? 1 : 0);

  for (let index = 0; index < n; index++) {
    const num = nums[index];
    const group = counts[index % k];
    const count = group.get(num) ?? 0;

    group.set(num, count + 1);
  }

  for (let xor = 0; xor < MAX_XOR; xor++) {
    const count = counts[k - 1].get(xor) ?? 0;

    dp[k - 1][xor] = getGroupCount(k - 1) - count;
  }

  for (let index = k - 2; index >= 0; index--) {
    const groupCount = getGroupCount(index);
    const nextMin = Math.min(...dp[index + 1]);

    for (let xor = 0; xor < MAX_XOR; xor++) {
      dp[index][xor] = groupCount + nextMin;

      for (const [num, count] of counts[index]) {
        const cost = groupCount - count;

        dp[index][xor] = Math.min(dp[index][xor], dp[index + 1][xor ^ num] + cost);
      }
    }
  }

  return dp[0][0];
};