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] < 210
Solution:
class Solution {
public int minChanges(int[] nums, int k) {
int n = nums.length;
int maxNum = 1024;
// freq[i][j] = in position i, how many times j occurs
int[][] freq = new int[k][maxNum + 1];
for (int i = 0; i < nums.length; i ++) {
int index = i % k;
freq[index][nums[i]] ++;
}
// dp[i] = numebr of elements that can remain unchanged for XOR product i
int[] dp = new int[2048];
Arrays.fill(dp, Integer.MIN_VALUE);
dp[0] = 0;
for (int i = 0; i < k; i ++) {
int maxPrev = 0;
for (int val : dp) maxPrev = Math.max(val, maxPrev);
// if we pick a number such that number ^ prevMax == i, we can at least save maxPrev elements
int[] dp2 = new int[2048];
Arrays.fill(dp2, maxPrev);
int[] posFreq = freq[i];
for (int num = 0; num <= maxNum; num ++) {
int count = posFreq[num];
if (count == 0) continue;
for (int prevXOR = 0; prevXOR <= maxNum ; prevXOR ++) {
dp2[num ^ prevXOR] = Math.max(dp2[num ^ prevXOR], count + dp[prevXOR]);
}
}
dp = dp2;
// System.out.println(Arrays.toString(dp));
}
return nums.length - dp[0];
}
}