Minimum Number of Operations to Make Array XOR Equal to K

Medium
724.

Minimum Number of Operations to Make Array XOR Equal to K

Minimum Number of Operations to Make Array XOR Equal to K is a medium coding problem on arrays and bit manipulation, asked in Amazon, Google and Flipkart interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minOperationsXor = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Operations to Make Array XOR Equal to K Solution

Minimum Number of Operations to Make Array XOR Equal to K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Number of Operations to Make Array XOR Equal to K is a medium coding problem on arrays and bit manipulation, asked in Amazon, Google and Flipkart interviews.

  • Difficulty: Medium
  • Topics: Arrays, Bit Manipulation
  • Asked at: Amazon, Google, Flipkart
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Minimum Number of Operations to Make Array XOR Equal to K

  1. Hint 1

    Flipping bit b of any element flips bit b of the array's XOR — it does not matter which element you pick.

  2. Hint 2

    So the question is only how many bits differ between the current XOR and k.

  3. Hint 3

    That count is the popcount of xor ^ k.

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")

Java

public static int minOperationsXor(int[] nums, int k) {
    int x = 0;
    for (int v : nums) x ^= v;
    return Integer.bitCount(x ^ k);
}

C++

int minOperationsXor(vector<int>& nums, int k) {
    int x = 0;
    for (int v : nums) x ^= v;
    return __builtin_popcount((unsigned) (x ^ k));
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Bit Manipulation