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:
0 to 1 or 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 <= 106Problem Overview: You’re given an integer array nums and a target value k. In one operation, you can flip any single bit of any element. The goal is to make the XOR of the entire array equal to k using the minimum number of operations.
Approach 1: Bit Manipulation (O(n) time, O(1) space)
Start by computing the XOR of all elements in the array. Call this value currentXor. If the final XOR must be k, then the difference between the two values is diff = currentXor ^ k. Every set bit in diff represents a bit position that must be flipped somewhere in the array.
Because flipping a single bit in any number toggles that bit in the overall XOR, each mismatched bit requires exactly one operation. Iterate through the bits of diff and count how many are set. That count is the minimum number of operations needed. This approach relies on core properties of bit manipulation and the XOR operator.
Approach 2: Count Set Bits (O(n) time, O(1) space)
This approach focuses directly on counting the mismatched bits after computing the array XOR. First iterate through the array and compute currentXor. Then calculate diff = currentXor ^ k. The number of required operations is simply the number of set bits in diff.
You can count these bits using built‑in popcount functions or classic techniques like repeatedly clearing the lowest set bit (diff &= diff - 1). Each set bit corresponds to one required flip operation. Since the integer size is fixed (typically 32 bits), the counting step is effectively constant time.
Recommended for interviews: The expected solution is the XOR difference + set bit count approach. Interviewers want to see that you understand how XOR aggregates bits across an array and how flipping one bit affects the final result. A brute-force bit-by-bit reasoning demonstrates understanding, but the optimized bit manipulation insight shows strong familiarity with XOR properties.
This approach involves using bit manipulation to find out which bits are different between the XOR of the array and k. For each differing bit, calculate the minimum number of flips needed across all elements to switch that bit in the resultant XOR.
We start by calculating the XOR sum of the array, XOR it with k to find the differing bits, and count each differing bit as an operation needed to make the elements' XOR equal to k.
Time Complexity: O(n), where n is the length of the array, since we only traverse it twice.
Space Complexity: O(1), as no additional data structures are used.
In this approach, the focus is on counting the set bits of two numbers (XOR sum and k) - i.e., how many bits are 1 in their binary representation. We aim to equalize the set bits count by flipping specific bits in nums.
We define a helper function to count the set bits of a number. We calculate XOR sum first, and then find the difference in set bit numbers compared to k.
Time Complexity: O(n + log(max(nums[i])))
Space Complexity: O(1).
We can perform a bitwise XOR operation on all elements in the array nums. The number of bits that differ from the binary representation of k in the result is the minimum number of operations.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Bit Manipulation | Time Complexity: O(n), where n is the length of the array, since we only traverse it twice. |
| Approach 2: Count Set Bits | Time Complexity: O(n + log(max(nums[i]))) |
| Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bit Manipulation with XOR Difference | O(n) | O(1) | General case; fastest way once you recognize XOR properties |
| Count Set Bits (Popcount) | O(n) | O(1) | Useful when built-in bit counting functions are available |
Minimum Number of Operations to Make Array XOR Equal to K | Easy | Leetcode 2997 | codestorywithMIK • codestorywithMIK • 7,271 views views
Watch 9 more video solutions →Practice Minimum Number of Operations to Make Array XOR Equal to K with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor