LeetCode 2997 - Minimum Number of Operations to Make Array XOR Equal to K

LeetCode Problem 2997

Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation

Solution

Problem Understanding

This problem asks us to transform an array so that the bitwise XOR of all elements becomes exactly k, while minimizing the number of operations.

An operation consists of selecting any element in the array and flipping exactly one bit in its binary representation. A bit flip changes a 0 to 1 or a 1 to 0. Since we may flip any bit position, including leading zero bits, we effectively have unlimited bit positions available.

The input consists of:

• nums, a 0-indexed integer array
• k, the desired final XOR value

The goal is to determine the minimum number of bit flips required so that:

$$nums[0] \oplus nums[1] \oplus ... \oplus nums[n-1] = k$$

where ⊕ denotes the XOR operation.

The constraints are important:

• nums.length <= 10^5
• nums[i] <= 10^6
• k <= 10^6

These constraints strongly suggest that we need an efficient solution, ideally linear time. Any brute-force approach that explores many combinations of bit flips would be infeasible.

The key observation is that XOR operates independently on each bit position. Since flipping one bit changes exactly one bit of the overall XOR, we can reason about each bit independently.

Several edge cases stand out immediately:

• The XOR of the array may already equal k, in which case the answer is 0.
• nums can contain zeros, meaning leading bits may need to be flipped.
• k may contain bits beyond the highest set bit of all numbers in nums, but the problem explicitly allows flipping leading zero bits.
• The array may contain only one element, meaning we directly transform that number into something that makes the XOR equal k.

Approaches

Brute Force Approach

A naive approach would attempt to explore possible sequences of bit flips until the XOR becomes k.

We could imagine treating each array state as a node in a graph, where each edge represents flipping one bit in one number. A breadth-first search could theoretically find the minimum number of operations.

This approach is correct because BFS guarantees the shortest path in an unweighted graph. However, it is completely impractical.

Each number has many possible bit positions to flip, and there are up to 10^5 numbers. Even restricting ourselves to around 20 bits, each state could branch into millions of possibilities. The number of reachable states grows exponentially, making this infeasible.

We need a more direct observation.

Key Insight

Let:

$$currentXor = nums[0] \oplus nums[1] \oplus ... \oplus nums[n-1]$$

Suppose we compare currentXor with k.

A single bit flip in any element changes exactly one bit in the total XOR.

Why?

Because XOR works bit by bit. If we flip bit i in one number, bit i of the total XOR toggles exactly once.

This means every mismatched bit between currentXor and k requires exactly one operation.

If a bit already matches, we do not need to touch it.

Therefore, the answer is simply:

$$\text{number of set bits in } (currentXor \oplus k)$$

The XOR operation identifies all differing bit positions. Counting the set bits tells us exactly how many operations are required.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores possible bit flips, infeasible for constraints
Optimal	O(n)	O(1)	Compute XOR difference and count differing bits

Algorithm Walkthrough

Optimal Algorithm

1. Compute the XOR of all elements in nums.

Initialize a variable current_xor = 0.

Iterate through every number in nums and continuously XOR it into current_xor.

This gives us the current XOR of the entire array. 2. Compute the XOR difference with k.

Calculate:

difference = current_xor ^ k

Any bit set to 1 in difference represents a mismatch between the current XOR and the target XOR. 3. Count the number of set bits in difference.

Each set bit corresponds to one required operation because one bit flip changes exactly one XOR bit.

We can count set bits using:

• Python: bit_count()
• Go: repeatedly remove the lowest set bit

4. Return the number of set bits.

This value is the minimum number of operations needed.

Why it works

The correctness relies on the independence of XOR bits.

Each bit position in the XOR result is independent of every other bit position. Flipping one bit in one element toggles exactly one bit in the total XOR. Therefore, each differing bit between current_xor and k must be fixed individually, and each requires exactly one operation.

Since one operation can only change one XOR bit, and every mismatched bit must be corrected, the minimum number of operations is exactly the number of differing bits.

Python Solution

from typing import List

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        current_xor = 0

        for number in nums:
            current_xor ^= number

        difference = current_xor ^ k

        return difference.bit_count()

The implementation follows the algorithm directly.

We first compute the XOR of the entire array using a running accumulator called current_xor. Since XOR is associative and commutative, the order of operations does not matter.

Next, we XOR current_xor with k to identify which bit positions differ. Every 1 bit in this result represents one mismatch.

Finally, bit_count() efficiently counts the number of set bits, which corresponds exactly to the minimum number of required operations.

Go Solution

func minOperations(nums []int, k int) int {
	currentXor := 0

	for _, num := range nums {
		currentXor ^= num
	}

	difference := currentXor ^ k
	operations := 0

	for difference > 0 {
		difference &= (difference - 1)
		operations++
	}

	return operations
}

The Go implementation follows the same logic as the Python solution.

One difference is that Go does not provide a built-in bit_count() method for integers in the same way Python does. Instead, we use Brian Kernighan's algorithm.

The expression:

difference &= (difference - 1)

removes the lowest set bit in each iteration. Therefore, the loop runs exactly once per set bit, making it efficient.

There are no concerns about integer overflow because the values remain comfortably within Go's integer range.

Worked Examples

Example 1

Input:

nums = [2,1,3,4]
k = 1

First, compute the XOR of all numbers.

Step	Number	Running XOR
Start	-	0
1	2	2
2	1	3
3	3	0
4	4	4

So:

current_xor = 4

Now compare with k.

difference = 4 ^ 1

Binary form:

4 = 100
1 = 001
-----------
  = 101

The result has 2 set bits.

Variable	Value
current_xor	4
k	1
difference	5 (101₂)
Set bits	2

Answer:

2

Example 2

Input:

nums = [2,0,2,0]
k = 0

Compute XOR.

Step	Number	Running XOR
Start	-	0
1	2	2
2	0	2
3	2	0
4	0	0

Now compare with k.

difference = 0 ^ 0 = 0

There are no differing bits.

Variable	Value
current_xor	0
k	0
difference	0
Set bits	0

Answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass through the array to compute XOR
Space	O(1)	Only a few integer variables are used

The dominant cost comes from iterating through nums once. Counting set bits takes constant time because integers are bounded in size, at most around 20 bits under the problem constraints. Therefore, the overall runtime is linear in the size of the array.

The algorithm uses only a few extra variables regardless of input size, so auxiliary space remains constant.

Test Cases

solution = Solution()

assert solution.minOperations([2, 1, 3, 4], 1) == 2  # Provided example 1
assert solution.minOperations([2, 0, 2, 0], 0) == 0  # Provided example 2

assert solution.minOperations([5], 5) == 0  # Single element already matches
assert solution.minOperations([5], 0) == 2  # Single element requires two bit flips

assert solution.minOperations([0], 7) == 3  # Flip leading zero bits
assert solution.minOperations([0, 0, 0], 0) == 0  # All zeros already valid

assert solution.minOperations([1, 2, 3], 0) == 0  # XOR already equals target
assert solution.minOperations([1, 2, 3], 7) == 3  # Multiple differing bits

assert solution.minOperations([1000000], 1000000) == 0  # Large value boundary
assert solution.minOperations([1000000], 0) > 0  # Large number bit differences

assert solution.minOperations([7, 7, 7], 7) == 0  # XOR already target
assert solution.minOperations([7, 7, 7], 0) == 3  # Requires multiple flips

Test	Why
[2,1,3,4], k=1	Validates provided example
[2,0,2,0], k=0	Validates no-operation case
[5], k=5	Single element already correct
[5], k=0	Single element requires changes
[0], k=7	Tests flipping leading zero bits
[0,0,0], k=0	All-zero edge case
[1,2,3], k=0	XOR already equals target
[1,2,3], k=7	Multiple differing bits
[1000000], k=1000000	Boundary value
[1000000], k=0	Large number transformation
[7,7,7], k=7	Repeated values
[7,7,7], k=0	Multiple required operations

Edge Cases

The XOR Already Equals k

One important edge case occurs when the current XOR of the array already matches the target value.

For example:

nums = [2,0,2,0]
k = 0

A buggy implementation might still attempt unnecessary operations. Our implementation handles this naturally because:

difference = current_xor ^ k = 0

The bit count becomes 0, so we correctly return no operations.

Leading Zero Bits Need Flipping

The problem explicitly states that leading zero bits may be flipped.

For example:

nums = [0]
k = 8

Binary representation:

0 = 0000
8 = 1000

Although 0 does not visibly contain that bit, we are allowed to flip higher-order bits. Our solution handles this automatically because XOR comparison works regardless of bit length.

Single Element Arrays

When the array contains only one number, the problem reduces to changing that value so its XOR equals k.

For example:

nums = [5]
k = 0

Since:

5 ^ 0 = 5

and 5 in binary is 101, we need exactly two bit flips.

The implementation handles this case naturally because the XOR accumulation works correctly even for arrays of length 1.

Multiple High Bit Differences

If k differs in several bit positions, every differing bit must be fixed independently.

For example:

nums = [0]
k = 15

Binary:

0    = 0000
15   = 1111
diff = 1111

There are four differing bits, meaning four required operations. Since one operation can only flip one bit, fewer operations are impossible. The implementation guarantees correctness by counting set bits exactly.