Watch 10 video solutions for Minimum Number of Operations to Make Array XOR Equal to K, a medium level problem involving Array, Bit Manipulation. This walkthrough by codestorywithMIK has 7,271 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |