Problem

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 0 to 1 or vice versa.

Return _theminimum number of operations required to make the bitwise _XOR _ofall 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.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3

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 <= 10^5
  • 0 <= nums[i] <= 10^6
  • 0 <= k <= 10^6

Solution

Method 1 – Bitwise Greedy (Count Bit Differences)

Intuition

Flipping a bit in any element lets us change the overall XOR. To reach k, we need to flip bits so that the XOR of all elements becomes k. The minimum number of operations is the number of bits that differ between the current XOR and k.

Approach

  1. Compute the XOR of all elements in nums.
  2. XOR this value with k to get the difference mask.
  3. Count the number of set bits in the mask; each set bit requires one flip.
  4. Return the count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include <vector>
using namespace std;
class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        int x = 0;
        for (int n : nums) x ^= n;
        int diff = x ^ k, ans = 0;
        while (diff) { ans += diff & 1; diff >>= 1; }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func minOperations(nums []int, k int) int {
    x := 0
    for _, n := range nums { x ^= n }
    diff, ans := x ^ k, 0
    for diff > 0 {
        ans += diff & 1
        diff >>= 1
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int minOperations(int[] nums, int k) {
        int x = 0;
        for (int n : nums) x ^= n;
        int diff = x ^ k, ans = 0;
        while (diff > 0) {
            ans += diff & 1;
            diff >>= 1;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun minOperations(nums: IntArray, k: Int): Int {
        var x = 0
        for (n in nums) x = x xor n
        var diff = x xor k
        var ans = 0
        while (diff > 0) {
            ans += diff and 1
            diff = diff shr 1
        }
        return ans
    }
}
1
2
3
4
5
6
7

class Solution:
    def minOperations(self, nums: list[int], k: int) -> int:
        x = 0
        for n in nums:
            x ^= n
        diff = x ^ k
        return bin(diff).count('1')
1
2
3
4
5
6

impl Solution {
    pub fn min_operations(nums: Vec<i32>, k: i32) -> i32 {
        let x = nums.iter().fold(0, |acc, &n| acc ^ n);
        (x ^ k).count_ones() as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    minOperations(nums: number[], k: number): number {
        let x = 0;
        for (const n of nums) x ^= n;
        let diff = x ^ k, ans = 0;
        while (diff > 0) {
            ans += diff & 1;
            diff >>= 1;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — n = length of nums.
  • 🧺 Space complexity: O(1) — only a few variables.