Minimum Number of Operations to Make Array XOR Equal to K
MedPrompt
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.
Example 1:
Input: nums = [2,1,3,4], k = 1
Output: 2
Explanation: 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.Example 2:
Input: nums = [2,0,2,0], k = 0
Output: 0
Explanation: The XOR of elements of the array is (2 XOR 0 XOR 2 XOR 0) == 0 == k. So no operation is needed.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1060 <= k <= 106
Approaches
2 approaches with complexity analysis and trade-offs.
This approach analyzes the problem one bit at a time. For each bit position, it determines if a flip is necessary to match the target k's corresponding bit. The total number of required flips across all bit positions gives the minimum number of operations.
Algorithm
- Initialize an
operationscounter to 0. - Iterate through each bit position
ifrom 0 up to a safe limit (e.g., 30). - For each bit
i, calculate thei-th bit of the current XOR sum ofnumsby checking the parity of the count of numbers with thei-th bit set. - Get the
i-th bit of the targetk. - If the two bits differ, increment the
operationscounter. - Return the total
operations.
Walkthrough
The core idea is that a flip at the i-th bit of any number in the array will flip the i-th bit of the total XOR sum of the array. We can iterate through each bit position and check if the bit of the current XOR sum matches the corresponding bit of k. If they don't match, one operation (a bit flip at that position) is required.
- Algorithm:
- Initialize an
operationscounter to 0. - Iterate through each bit position
ifrom 0 up to a safe limit (e.g., 30, since the maximum value ofnums[i]andkis10^6, which is less than2^20). - For each bit position
i, calculate thei-th bit of the current XOR sum ofnums. This can be done by iterating through all numbers innumsand counting how many have thei-th bit set. If the count is odd, the XOR sum'si-th bit is 1; otherwise, it's 0. - Get the
i-th bit of the target valuek. - If the calculated
i-th bit of the XOR sum differs from thei-th bit ofk, it means we need to perform one flip at this bit position. Increment theoperationscounter. - After checking all relevant bit positions, the
operationscounter will hold the minimum number of operations.
- Initialize an
class Solution { public int minOperations(int[] nums, int k) { int operations = 0; // Max value is 10^6, which is < 2^20. Checking up to 30 bits is safe. for (int i = 0; i < 31; i++) { int currentXorBit = 0; for (int num : nums) { // Check if the i-th bit is set in num if (((num >> i) & 1) == 1) { currentXorBit ^= 1; } } // Get the i-th bit of k int kBit = (k >> i) & 1; // If the bits don't match, one operation is needed for this bit position if (currentXorBit != kBit) { operations++; } } return operations; }}Complexity
Time
O(N * M), where N is the number of elements in `nums` and M is the number of bits considered (e.g., 31). The nested loops (iterating through bits and then through the array) result in this complexity.
Space
O(1), as we only use a few variables to store intermediate results like the current bit and the total operation count.
Trade-offs
Pros
Conceptually straightforward, breaking the problem down by individual bits.
Does not require deep insights into the aggregate properties of XOR.
Cons
Inefficient due to the nested loop structure, leading to a higher time complexity.
It re-scans the entire array for each bit position, which is redundant.
This highly efficient approach leverages the properties of the XOR operation to find a direct solution. It first computes the XOR sum of the entire array and then compares it with k. The number of differing bits between the array's XOR sum and k directly corresponds to the minimum number of operations required.
Algorithm
- Calculate the bitwise XOR sum of all elements in
nums, let's call itcurrent_xor. - Calculate the XOR difference between the result and the target:
diff = current_xor ^ k. - Count the number of set bits (1s) in
diff. - The resulting count is the minimum number of operations.
Walkthrough
The fundamental insight is that flipping the i-th bit of any element in the array has the precise effect of flipping the i-th bit of the total XOR sum of the array. To change the total XOR sum from its initial value, current_xor, to the target value k, we must flip exactly those bits where current_xor and k differ.
The bits where two numbers differ are the bits that are set to 1 in their XOR result. Therefore, the problem reduces to finding the number of set bits (also known as population count or Hamming weight) in the value current_xor XOR k.
- Algorithm:
- Calculate the bitwise XOR sum of all elements in the
numsarray. Let's call thiscurrent_xor. - Calculate the difference between the current XOR sum and the target
kusing XOR:diff = current_xor ^ k. Thisdiffvalue has a1at each bit position that needs to be flipped. - Count the number of set bits (1s) in
diff. This count is the minimum number of operations, as each operation can fix one incorrect bit. - Return the count.
- Calculate the bitwise XOR sum of all elements in the
class Solution { public int minOperations(int[] nums, int k) { int currentXor = 0; for (int num : nums) { currentXor ^= num; } // The value `currentXor ^ k` gives a number where each set bit // represents a bit that needs to be flipped in the total XOR sum. // The number of set bits is the number of required flips. return Integer.bitCount(currentXor ^ k); }}Here is an alternative implementation for counting set bits without using the built-in Integer.bitCount:
class Solution { public int minOperations(int[] nums, int k) { int currentXor = 0; for (int num : nums) { currentXor ^= num; } int diff = currentXor ^ k; int operations = 0; // Using Brian Kernighan's algorithm to count set bits while (diff > 0) { // This clears the least significant bit diff &= (diff - 1); operations++; } return operations; }}Complexity
Time
O(N + M), where N is the number of elements in `nums` and M is the number of bits in the integer type (e.g., 32). The first loop to compute the XOR sum takes O(N). Counting the bits takes O(M) time. Since N is typically much larger than M, the complexity is effectively O(N).
Space
O(1), as the algorithm only requires a few variables to store the running XOR sum and the final count.
Trade-offs
Pros
Extremely efficient with a time complexity linear in the size of the input array.
Provides an elegant and concise solution by fully utilizing the properties of the XOR operation.
Cons
The solution is not immediately obvious and requires a solid understanding of bitwise operations to derive.
Solutions
Solution
class Solution {public int minOperations(int[] nums, int k) { for (int x : nums) { k ^= x; } return Integer.bitCount(k); }}class Solution {public: int minOperations(vector<int> &nums, int k) { for (int x : nums) { k ^= x; } return __builtin_popcount(k); }};class Solution: def minOperations( self, nums: List[int], k: int) -> int: return reduce(xor, nums, k). bit_count()Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.