Welcome to Subscribe On Youtube
1787. Make the XOR of All Segments Equal to Zero
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 <= 20000 <= nums[i] < 210
Solutions
-
class Solution { public int minChanges(int[] nums, int k) { int n = 1 << 10; Map<Integer, Integer>[] cnt = new Map[k]; Arrays.setAll(cnt, i -> new HashMap<>()); int[] size = new int[k]; for (int i = 0; i < nums.length; ++i) { int j = i % k; cnt[j].merge(nums[i], 1, Integer::sum); size[j]++; } int[] f = new int[n]; final int inf = 1 << 30; Arrays.fill(f, inf); 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 { public: int minChanges(vector<int>& nums, int k) { int n = 1 << 10; 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, 1 << 30); 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]; } }; -
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] -
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 := slices.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] }