Minimum Number of Operations to Make Array XOR Equal to K
Medium
You are given a 0-indexed integer array nums and a positive integer k.
You can apply the following operation on the array any number of times:
- Choose any element of the array and flip a bit in its binary representation. Flipping a bit means changing a
0to1or vice versa.
Return the minimum number of operations required to make the bitwise XOR of all elements of the final array equal to k.
Note that you can flip leading zero bits in the binary representation of elements. For example, for the number (101)2 you can flip the fourth bit and obtain (1101)2.
For example:
nums = [2,1,3,4], k = 1 should return 2 because:
We can do the following operations:
- Choose element 2 which is 3 ==
(011)2, we flip the first bit and we obtain(010)2 == 2. nums becomes[2,1,2,4]. - Choose element 0 which is 2 ==
(010)2, we flip the third bit and we obtain(110)2 = 6. nums becomes[6,1,2,4].
The XOR of elements of the final array is (6 XOR 1 XOR 2 XOR 4) == 1 == k.
It can be shown that we cannot make the XOR equal to k in less than 2 operations.
nums = [2,0,2,0], k = 0 should return 0 because The XOR of elements of the array is (2 XOR 0 XOR 2 XOR 0) == 0 == k. So no operation is needed.
Solution
Naive Approach
A brute force approach would be to try all possible combinations of bit flips for each element in the array and check if the XOR of all elements equals k. Since there are up to 10^5 elements, and each element can be up to 10^6, there are a huge number of possible flip combinations to explore, making this solution infeasible.
Complexity:
- Time Complexity: O(2^(N * B)), where N is the number of elements in
numsand B is the maximum number of bits in any number (10^6 has around 20 bits). - Space Complexity: O(1)
Optimal Approach
The key insight is that we don't need to try all possible bit flips. We just need to find the XOR of all the numbers in the original array, and then determine how many bits differ between the XOR result and the target value k.
- Calculate the XOR of all numbers in the
numsarray. Let's call thisxor_sum. - Calculate the XOR between
xor_sumandk. This XOR result will represent the bits that need to be flipped to make the XOR of the array equal tok. - Count the number of set bits (1s) in the result from step 2. This count represents the minimum number of operations required.
Example:
nums = [2, 1, 3, 4], k = 1
xor_sum = 2 ^ 1 ^ 3 ^ 4 = 4xor_sum ^ k = 4 ^ 1 = 5- The binary representation of 5 is
101. The number of set bits is 2.
Therefore, the minimum number of operations is 2.
Edge Cases:
- If the XOR of the original array equals
k, the number of operations is 0. - The numbers can have leading zeros in their binary representations.
Code:
def min_operations(nums, k):
xor_sum = 0
for num in nums:
xor_sum ^= num
xor_diff = xor_sum ^ k
operations = 0
while xor_diff > 0:
operations += xor_diff & 1
xor_diff >>= 1
return operations
class Solution {
public int minOperations(int[] nums, int k) {
int xorSum = 0;
for (int num : nums) {
xorSum ^= num;
}
int xorDiff = xorSum ^ k;
int operations = 0;
while (xorDiff > 0) {
operations += xorDiff & 1;
xorDiff >>= 1;
}
return operations;
}
}
Complexity:
- Time Complexity: O(N + B), where N is the number of elements in
numsand B is the maximum number of bits in any number. Since B is capped at the maximum possible value of any element innumsork, this can be simplified to O(N). - Space Complexity: O(1)
