Minimum Number of Operations to Make Array XOR Equal to K — Medium Problem & Solution

Problem statement

In one operation you may flip any single bit of any single element of nums — including a leading zero bit.

Return the minimum number of operations after which the XOR of the whole array equals k.

Example 1

Input: nums = [2,1,3,4], k = 1
Output: 2
Explanation: The array XORs to 4; turning that into 1 takes two bit flips.

Example 2

Input: nums = [2,0,2,0], k = 0
Output: 0
Explanation: The array already XORs to 0.

Example 3

Input: nums = [7], k = 7
Output: 0

Constraints

• 1 <= nums.length <= 100000
• 0 <= nums[i] <= 1000000
• 0 <= k <= 1000000

How to solve Minimum Number of Operations to Make Array XOR Equal to K

One bit flip anywhere toggles exactly one bit of the overall XOR, so each differing bit costs exactly one operation and no operation fixes two bits at once.

Approach

1. XOR all of nums into a single value x.
2. Compute x ^ k, whose set bits are exactly the positions where x and k disagree.
3. Return the number of set bits in it.

Why it works

XOR is bitwise and associative, so flipping bit b of some element flips bit b of the total and leaves every other bit alone. Reaching k therefore requires exactly one flip per differing bit, and that many suffice.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Trying to decide which element to modify is wasted effort — any element works.
• Counting the bits of x or of k rather than of their XOR answers a different question.

Reference solution

Python

from typing import List

def minOperationsXor(nums: List[int], k: int) -> int:
    x = 0
    for v in nums:
        x ^= v
    return bin(x ^ k).count("1")

JavaScript

var minOperationsXor = function(nums, k) {
    var x = 0;
    for (var i = 0; i < nums.length; i++) x ^= nums[i];
    var diff = x ^ k, count = 0;
    while (diff > 0) {
        count += diff & 1;
        diff >>= 1;
    }
    return count;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Work Sessions to Finish the Tasks Medium
• Remove All Ones With Row and Column Flips Medium
• Minimum Impossible OR Medium
• Maximum OR Medium
• Minimum Array End Medium
• Number of Wonderful Substrings Medium