Welcome to Subscribe On Youtube

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

############

class Solution {
    public int minChanges(int[] nums, int k) {
        int n = 1 << 10;
        Map<Integer, Integer>[] cnt = new Map[k];
        int[] size = new int[k];
        for (int i = 0; i < k; ++i) {
            cnt[i] = new HashMap<>();
        }
        for (int i = 0; i < nums.length; ++i) {
            cnt[i % k].put(nums[i], cnt[i % k].getOrDefault(nums[i], 0) + 1);
            size[i % k]++;
        }
        int[] f = new int[n];
        Arrays.fill(f, 0x3f3f3f3f);
        f[0] = 0;
        for (int i = 0; i < k; ++i) {
            int[] g = new int[n];
            Arrays.fill(g, min(f) + size[i]);
            for (int j = 0; j < n; ++j) {
                for (var e : cnt[i].entrySet()) {
                    int v = e.getKey(), c = e.getValue();
                    g[j] = Math.min(g[j], f[j ^ v] + size[i] - c);
                }
            }
            f = g;
        }
        return f[0];
    }

    private int min(int[] arr) {
        int mi = arr[0];
        for (int v : arr) {
            mi = Math.min(mi, v);
        }
        return mi;
    }
}

  • class Solution:
    def minChanges(self, nums: List[int], k: int) -> int:
        n = 1 << 10
        cnt = [Counter() for _ in range(k)]
        size = [0] * k
        for i, v in enumerate(nums):
            cnt[i % k][v] += 1
            size[i % k] += 1
        f = [inf] * n
        f[0] = 0
        for i in range(k):
            g = [min(f) + size[i]] * n
            for j in range(n):
                for v, c in cnt[i].items():
                    g[j] = min(g[j], f[j ^ v] + size[i] - c)
            f = g
        return f[0]



  • class Solution {
public:
    int minChanges(vector<int>& nums, int k) {
        int n = 1 << 10;
        vector<unordered_map<int, int>> cnt(k);
        vector<int> size(k);
        for (int i = 0; i < nums.size(); ++i) {
            cnt[i % k][nums[i]]++;
            size[i % k]++;
        }
        vector<int> f(n, 0x3f3f3f3f);
        f[0] = 0;
        for (int i = 0; i < k; ++i) {
            int mi = *min_element(f.begin(), f.end());
            vector<int> g(n, mi + size[i]);
            for (int j = 0; j < n; ++j) {
                for (auto& [v, c] : cnt[i]) {
                    g[j] = min(g[j], f[j ^ v] + size[i] - c);
                }
            }
            f = move(g);
        }
        return f[0];
    }
};

  • func minChanges(nums []int, k int) int {
	n := 1 << 10
	cnt := make([]map[int]int, k)
	for i := range cnt {
		cnt[i] = map[int]int{}
	}
	size := make([]int, k)
	for i, v := range nums {
		cnt[i%k][v]++
		size[i%k]++
	}
	f := make([]int, n)
	for i := 1; i < n; i++ {
		f[i] = 0x3f3f3f3f
	}
	for i, sz := range size {
		g := make([]int, n)
		x := min(f...) + sz
		for i := range g {
			g[i] = x
		}
		for j := 0; j < n; j++ {
			for v, c := range cnt[i] {
				g[j] = min(g[j], f[j^v]+sz-c)
			}
		}
		f = g
	}
	return f[0]
}

func min(a ...int) int {
	mi := a[0]
	for _, v := range a {
		if mi > v {
			mi = v
		}
	}
	return mi
}

All Problems

All Solutions