Formatted question description: https://leetcode.ca/all/1787.html

1787. Make the XOR of All Segments Equal to Zero

Level

Hard

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 <= 2000
  • 0 <= nums[i] < 2^10

Solution

Divide the elements in nums into k groups, where all the elements in the same group have indices with the same remainder when divided by k.

Create a 2D array dp with k + 1 rows and 1 << 10 columns, where dp[i][j] represents the minimum number of elements to change for the i-th group to make XOR value equal to j. For i = 0, there is dp[0][0] = 0 and dp[0][j] = INF when j > 0.

For 0 <= i < k, initialize dp[i + 1] with min(dp[i]) + size[i]. For 0 <= j < 1 << 10, if dp[i][j] != INF, update the values in dp[i + 1]. For val' in the i + 1-th group, enumerate previous val in the i-th group, and update dp[i + 1][val ^ val'] accordingly.

Finally, return dp[k][0].

class Solution {
    public int minChanges(int[] nums, int k) {
        final int INF = 0x3f3f3f3f;
        final int MAX = 1 << 10;
        int length = nums.length;
        Map<Integer, Integer>[] groups = new Map[k];
        for (int i = 0; i < k; i++)
            groups[i] = new HashMap<Integer, Integer>();
        int[] size = new int[k];
        for (int i = 0; i < k; i++) {
            for (int j = i; j < length; j += k) {
                groups[i].put(nums[j], groups[i].getOrDefault(nums[j], 0) + 1);
                size[i]++;
            }
        }
        int[][] dp = new int[k + 1][MAX];
        Arrays.fill(dp[0], INF);
        dp[0][0] = 0;
        for (int i = 0; i < k; i++) {
            int low = Arrays.stream(dp[i]).min().getAsInt();
            Arrays.fill(dp[i + 1], low + size[i]);
            for (int j = 0; j < MAX; j++) {
                if (dp[i][j] != INF) {
                    for (Map.Entry<Integer, Integer> entry : groups[i].entrySet()) {
                        int key = entry.getKey(), value = entry.getValue();
                        int next = key ^ j;
                        dp[i + 1][next] = Math.min(dp[i + 1][next], dp[i][j] + size[i] - value);
                    }
                }
            }
        }
        return dp[k][0];
    }
}

All Problems

All Solutions