Minimize XOR

medium bitwise greedy

Problem

You are given two positive integers num1 and num2. Construct a positive integer x that has exactly as many set bits (1s in binary) as num2, placed so that x XOR num1 is as small as possible. The optimal x is unique; return it.

Inputnum1 = 9, num2 = 30

Output15

num2 = 11110 (binary) has four 1s. Matching num1 = 1001 at bits 3 and 0, then filling the lowest zeros (bits 1 and 2) gives x = 1111 = 15, and 15 XOR 9 = 6 is the minimum possible.

num1 (integer 1–1023)

num2 (integer 1–1023)

def minimize_xor(num1, num2):
    k = bin(num2).count("1")
    x = 0
    for b in range(31, -1, -1):
        if k and (num1 >> b) & 1:
            x |= 1 << b
            k -= 1
    b = 0
    while k:
        if not (x >> b) & 1:
            x |= 1 << b
            k -= 1
        b += 1
    return x

function minimizeXor(num1, num2) {
  let k = 0;
  for (let b = 0; b < 32; b++) if ((num2 >> b) & 1) k++;
  let x = 0;
  for (let b = 31; b >= 0; b--) {
    if (k > 0 && ((num1 >> b) & 1)) {
      x |= 1 << b;
      k--;
    }
  }
  for (let b = 0; k > 0; b++) {
    if (!((x >> b) & 1)) {
      x |= 1 << b;
      k--;
    }
  }
  return x;
}

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

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

Explanation

The number of 1s in x is fixed: it must equal the set-bit count of num2. Think of that count as a budget k of 1-bits you are allowed to place. The only freedom is where to place them, and the goal is to make x XOR num1 small.

XOR is decided column by column: position b contributes 2^b to the XOR exactly when x and num1 disagree there. Because 2^b is larger than the sum of all lower powers combined (2^b > 2^(b-1) + ... + 1), cancelling a high disagreement is always worth more than anything that happens below it. That is why a greedy high-to-low pass is safe.

So the algorithm runs in two phases. Phase 1: scan bits from high to low; wherever num1 has a 1 and budget remains, copy that 1 into x — those columns now XOR to 0. Phase 2: if budget is still left over, every extra 1 must land where num1 has a 0 and will add 2^b to the XOR, so we drop the leftovers into the lowest zero positions of x, the cheapest spots available.

Walk through the default example, num1 = 9 (1001) and num2 = 30 (11110, four 1s). The budget is 4. Phase 1 claims num1's set bits 3 and 0, making x = 1001 with 2 ones still owed. Phase 2 finds bit 0 already taken, then fills bits 1 and 2: x = 1111 = 15. The result is 15 XOR 9 = 6, and no other 4-one number does better.

Both passes touch each of the 32 bit positions at most once, so the running time is proportional to the word size — O(log max(num1, num2)), effectively constant — and only a handful of integer variables are kept, so space is O(1).

Time: O(log max(num1, num2)) Space: O(1)