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
Hint 1
XOR is smallest when
xagrees withnum1on the highest bits.Hint 2
So spend the budget of set bits on
num1's bits from the top down.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
- Count the set bits of
num2; call itneed. - Walk
bfrom 30 down to 0: ifnum1has bitbandneed > 0, set it inxand decrementneed. - Walk
bfrom 0 upward: ifxdoes not yet have bitbandneed > 0, set it and decrementneed. - 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
needhits 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 xJava
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