Minimize XOR — Medium Problem & Solution

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

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

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

More greedy 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