1787. Make the XOR of All Segments Equal to Zero LeetCode Solution
In this guide, you will get 1787. Make the XOR of All Segments Equal to Zero LeetCode Solution with the best time and space complexity. The solution to Make the XOR of All Segments Equal to Zero problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Make the XOR of All Segments Equal to Zero
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].
1787. Make the XOR of All Segments Equal to Zero LeetCode Solution in C++
class Solution {
public:
int minChanges(vector<int>& nums, int k) {
constexpr int kMax = 1024;
const int n = nums.size();
// counts[i] := the counter that maps at the i-th position
vector<unordered_map<int, int>> counts(k);
// dp[i][j] := the minimum number of elements to change s.t. XOR(nums[i..k -
// 1]) is j
vector<vector<int>> dp(k, vector<int>(kMax, n));
for (int i = 0; i < n; ++i)
++counts[i % k][nums[i]];
auto countAt = [n, k](int i) -> int { return n / k + (n % k > i ? 1 : 0); };
// Initialize the DP array.
for (int j = 0; j < kMax; ++j)
dp[k - 1][j] =
countAt(k - 1) - (counts[k - 1].contains(j) ? counts[k - 1][j] : 0);
for (int i = k - 2; i >= 0; --i) {
// The worst-case scenario is changing all the i-th position numbers to a
// non-existent value in the current bucket.
const int changeAll = countAt(i) + ranges::min(dp[i + 1]);
for (int j = 0; j < kMax; ++j) {
dp[i][j] = changeAll;
for (const auto& [num, freq] : counts[i]) {
// the cost to change every number in the i-th position to `num`
const int cost = countAt(i) - freq;
dp[i][j] = min(dp[i][j], dp[i + 1][j ^ num] + cost);
}
}
}
return dp[0][0];
}
}; /* code provided by PROGIEZ */
1787. Make the XOR of All Segments Equal to Zero LeetCode Solution in Java
class Solution {
public int minChanges(int[] nums, int k) {
final int kMax = 1024;
final int n = nums.length;
// counts[i] := the counter that maps at the i-th position
Map<Integer, Integer>[] counts = new Map[k];
// dp[i][j] := the minimum number of elements to change s.t. XOR(nums[i..k - 1]) is j
int[][] dp = new int[k][kMax];
for (int i = 0; i < k; ++i)
counts[i] = new HashMap<>();
for (int i = 0; i < n; ++i)
counts[i % k].merge(nums[i], 1, Integer::sum);
Arrays.stream(dp).forEach(A -> Arrays.fill(A, n));
// Initialize the DP array.
for (int j = 0; j < kMax; ++j)
dp[k - 1][j] = countAt(n, k, k - 1) - counts[k - 1].getOrDefault(j, 0);
for (int i = k - 2; i >= 0; --i) {
// The worst-case scenario is changing all the i-th position numbers to a
// non-existent value in the current bucket.
final int changeAll = countAt(n, k, i) + Arrays.stream(dp[i + 1]).min().getAsInt();
for (int j = 0; j < kMax; ++j) {
dp[i][j] = changeAll;
for (Map.Entry<Integer, Integer> entry : counts[i].entrySet()) {
final int num = entry.getKey();
final int freq = entry.getValue();
// the cost to change every number in the i-th position to `num`
final int cost = countAt(n, k, i) - freq;
dp[i][j] = Math.min(dp[i][j], dp[i + 1][j ^ num] + cost);
}
}
}
return dp[0][0];
}
private int countAt(int n, int k, int i) {
return n / k + (n % k > i ? 1 : 0);
}
} // code provided by PROGIEZ
1787. Make the XOR of All Segments Equal to Zero LeetCode Solution in Python
class Solution:
def minChanges(self, nums: list[int], k: int) -> int:
kMax = 1024
n = len(nums)
# counts[i] := the counter that maps at the i-th position
counts = [collections.Counter() for _ in range(k)]
# dp[i][j] := the minimum number of elements to change s.t. XOR(nums[i..k - 1]) is j
dp = [[n] * kMax for _ in range(k)]
for i, num in enumerate(nums):
counts[i % k][num] += 1
def countAt(i: int) -> int:
return n // k + (1 if n % k > i else 0)
# Initialize the DP array.
for j in range(kMax):
dp[k - 1][j] = countAt(k - 1) - counts[k - 1][j]
for i in range(k - 2, -1, -1):
# The worst-case scenario is changing all the i-th position numbers to a
# non-existent value in the current bucket.
changeAll = countAt(i) + min(dp[i + 1])
for j in range(kMax):
dp[i][j] = changeAll
for num, freq in counts[i].items():
# the cost to change every number in the i-th position to `num`
cost = countAt(i) - freq
dp[i][j] = min(dp[i][j], dp[i + 1][j ^ num] + cost)
return dp[0][0] # code by PROGIEZ
