# Minimum Number of Operations to Make Array XOR Equal to K
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-operations-to-make-array-xor-equal-to-k)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-operations-to-make-array-xor-equal-to-k
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
**Companies:** [American Express](https://scaleengineer.com/companies/american-express)
---
## 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 _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 <= 105`
* `0 <= nums[i] <= 106`
* `0 <= k <= 106`

# Approaches
## Bit-by-Bit Analysis
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.
**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.
**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.
### Explanation
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:**
    1.  Initialize an `operations` counter to 0.
    2.  Iterate through each bit position `i` from 0 up to a safe limit (e.g., 30, since the maximum value of `nums[i]` and `k` is `10^6`, which is less than `2^20`).
    3.  For each bit position `i`, calculate the `i`-th bit of the current XOR sum of `nums`. This can be done by iterating through all numbers in `nums` and counting how many have the `i`-th bit set. If the count is odd, the XOR sum's `i`-th bit is 1; otherwise, it's 0.
    4.  Get the `i`-th bit of the target value `k`.
    5.  If the calculated `i`-th bit of the XOR sum differs from the `i`-th bit of `k`, it means we need to perform one flip at this bit position. Increment the `operations` counter.
    6.  After checking all relevant bit positions, the `operations` counter will hold the minimum number of operations.

```java
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;
    }
}
```
### Algorithm
*   Initialize an `operations` counter to 0.
*   Iterate through each bit position `i` from 0 up to a safe limit (e.g., 30).
*   For each bit `i`, calculate the `i`-th bit of the current XOR sum of `nums` by checking the parity of the count of numbers with the `i`-th bit set.
*   Get the `i`-th bit of the target `k`.
*   If the two bits differ, increment the `operations` counter.
*   Return the total `operations`.

## Optimized XOR Sum and Bit Count
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.
**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.
**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.
### Explanation
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:**
    1.  Calculate the bitwise XOR sum of all elements in the `nums` array. Let's call this `current_xor`.
    2.  Calculate the difference between the current XOR sum and the target `k` using XOR: `diff = current_xor ^ k`. This `diff` value has a `1` at each bit position that needs to be flipped.
    3.  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.
    4.  Return the count.

```java
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`:
```java
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;
    }
}
```
### Algorithm
*   Calculate the bitwise XOR sum of all elements in `nums`, let's call it `current_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.

# Solutions
### Java

```java
class Solution {
public
  int minOperations(int[] nums, int k) {
    for (int x : nums) {
      k ^= x;
    }
    return Integer.bitCount(k);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minOperations(vector<int> &nums, int k) {
    for (int x : nums) {
      k ^= x;
    }
    return __builtin_popcount(k);
  }
};

```

### Python

```python
class Solution:
    def minOperations(
        self, nums: List[int], k: int) -> int: return reduce(xor, nums, k). bit_count()

```