Minimize XOR

Medium
732.

Minimize XOR

Minimize XOR is a medium coding problem on greedy and bit manipulation, asked in Amazon, Google and Samsung interviews.

Return the integer x such that x has the same number of set bits as num2 and x XOR num1 is as small as possible.

The answer is unique.

Example 1

Input
num1 = 3, num2 = 5
Output
3
Explanation
5 has two set bits, and 3 also has two — making the XOR zero.

Example 2

Input
num1 = 1, num2 = 12
Output
3
Explanation
12 has two set bits; 3 keeps num1's bit 0 and adds the cheapest extra bit.

Example 3

Input
num1 = 25, num2 = 72
Output
24
Explanation
72 has two set bits, and 24 shares num1's two highest bits.

Constraints

  • 1 <= num1, num2 <= 1000000000
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} num1
 * @param {number} num2
 * @return {number}
 */
var minimizeXor = function(num1, num2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimize XOR — Solution in Python, Java & C++

Minimize XOR solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.

Minimize XOR is a medium coding problem on greedy and bit manipulation, asked in Amazon, Google and Samsung interviews.

  • Difficulty: Medium
  • Topics: Greedy, Bit Manipulation
  • Asked at: Amazon, Google, Samsung
  • 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

Return the integer x such that x has the same number of set bits as num2 and x XOR num1 is as small as possible.

The answer is unique.

Example 1

Input: num1 = 3, num2 = 5
Output: 3
Explanation: 5 has two set bits, and 3 also has two — making the XOR zero.

Example 2

Input: num1 = 1, num2 = 12
Output: 3
Explanation: 12 has two set bits; 3 keeps num1's bit 0 and adds the cheapest extra bit.

Example 3

Input: num1 = 25, num2 = 72
Output: 24
Explanation: 72 has two set bits, and 24 shares num1's two highest bits.

Constraints

  • 1 <= num1, num2 <= 1000000000

Hints for Minimize XOR

  1. Hint 1

    XOR is smallest when x agrees with num1 on the highest bits.

  2. Hint 2

    So spend the budget of set bits on num1's bits from the top down.

  3. Hint 3

    If bits are left over, add them at the lowest free positions, where they cost the least.

How to solve Minimize XOR

Two greedy passes. First reuse num1's set bits from the most significant downward, because matching a high bit removes the largest possible contribution to the XOR. Then, if the budget is not exhausted, set the lowest free bits, which add the smallest possible contribution.

Approach

  1. Count the set bits of num2; call it need.
  2. Walk b from 30 down to 0: if num1 has bit b and need > 0, set it in x and decrement need.
  3. Walk b from 0 upward: if x does not yet have bit b and need > 0, set it and decrement need.
  4. Return x.

Why it works

Matching num1's bit b saves 2^b from the XOR, so the savings are maximised by taking the highest matches first. Any bit set where num1 has none adds 2^b, so those should be as low as possible. The two passes never conflict because the second only considers positions the first left clear.

Complexity

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

Pitfalls

  • Running out of budget mid-way is expected — the loops must stop when need hits zero.
  • Setting leftover bits from the top down maximises the XOR instead of minimising it.
  • num2's value beyond its popcount is irrelevant; only the count matters.

Reference solution

Python

def minimizeXor(num1: int, num2: int) -> int:
    need = bin(num2).count("1")
    x = 0
    for b in range(30, -1, -1):
        if need == 0:
            break
        if (num1 >> b) & 1:
            x |= 1 << b
            need -= 1
    for b in range(31):
        if need == 0:
            break
        if not ((x >> b) & 1):
            x |= 1 << b
            need -= 1
    return x

Java

public static int minimizeXor(int num1, int num2) {
    int need = Integer.bitCount(num2);
    int x = 0;
    for (int b = 30; b >= 0 && need > 0; b--) {
        if (((num1 >> b) & 1) == 1) { x |= 1 << b; need--; }
    }
    for (int b = 0; b <= 30 && need > 0; b++) {
        if (((x >> b) & 1) == 0) { x |= 1 << b; need--; }
    }
    return x;
}

C++

int minimizeXor(int num1, int num2) {
    int need = __builtin_popcount((unsigned) num2);
    int x = 0;
    for (int b = 30; b >= 0 && need > 0; b--) {
        if ((num1 >> b) & 1) { x |= 1 << b; need--; }
    }
    for (int b = 0; b <= 30 && need > 0; b++) {
        if (!((x >> b) & 1)) { x |= 1 << b; need--; }
    }
    return x;
}

JavaScript

var minimizeXor = function(num1, num2) {
    var need = 0, t = num2;
    while (t > 0) { need += t & 1; t >>= 1; }
    var x = 0;
    for (var b = 30; b >= 0 && need > 0; b--) {
        if ((num1 >> b) & 1) { x |= 1 << b; need--; }
    }
    for (var c = 0; c <= 30 && need > 0; c++) {
        if (((x >> c) & 1) === 0) { x |= 1 << c; need--; }
    }
    return x;
};

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

All 264 greedy problems · the whole catalogue

Learn the technique: Greedy Algorithms · Bit Manipulation