Minimize XOR solution and explanation
IBM
Google
9 more videos on this problem
Minimize XOR | 2 Detailed Approaches | Dry Runs | Leetcode 2429 | codestorywithMIKcodestorywithMIK · 52:17 · 11K views
Minimize XOR | Leetcode 2429Techdose · 13:04 · 8K views
Minimize XOR - Leetcode 2429 - PythonNeetCodeIO · 12:17 · 8K views
2429. Minimize XOR | Bit ManipulationAryan Mittal · 13:52 · 2K views
2429. Minimize XOR (Leetcode Medium)Programming Live with Larry · 6:59 · 1K views
Daily Leetcode #1751: Jan 15, 2025 - 2429. Minimize XORProgramming Live with Larry · 19:42 · 349 views
2429. Minimize XOR | Leetcode Daily ChallengeEthos Typos · 13:42 · 237 views
Leetcode | 2429 Minimize XOR | Java | Bit Manipulation| Simple ApproachCakot Coding · 18:34 · 178 views
LeetCode 2429 Minimize XOR | Bit Manipulation | Greedy | Asked in AdobeCode Harmony · 23:52 · 137 views
LeetCode Minimize XOR Solution | 2429 | Step-by-Step Explanation | Code CrackCode Crack · 5:19 · 129 views
The problem
Given two positive integers num1 and num2, find the positive integer x such that:
xhas the same number of set bits asnum2, and- The value
x XOR num1is minimal.
Note that XOR is the bitwise XOR operation.
Return the integer x. The test cases are generated such that x is uniquely determined.
The number of set bits of an integer is the number of 1's in its binary representation.
Example 1:
Input: num1 = 3, num2 = 5
Output: 3
Explanation:
The binary representations of num1 and num2 are 0011 and 0101, respectively.
The integer 3 has the same number of set bits as num2, and the value 3 XOR 3 = 0 is minimal.
Example 2:
Input: num1 = 1, num2 = 12
Output: 3
Explanation:
The binary representations of num1 and num2 are 0001 and 1100, respectively.
The integer 3 has the same number of set bits as num2, and the value 3 XOR 1 = 2 is minimal.
Constraints:
1 <= num1, num2 <= 109
Approach overview
Problem Overview: Given two integers num1 and num2, construct a number x such that x has the same number of set bits (1s) as num2 while minimizing x XOR num1. The challenge is choosing which bit positions to set so the XOR difference with num1 stays as small as possible.
Approach 1: Greedy Bit Setting Strategy (O(1) time, O(1) space)
This approach relies on a simple observation about XOR: the result is smallest when the most significant bits match. First compute the number of set bits required using popcount(num2). Then iterate through the bits of num1 from the most significant bit to the least significant bit. Whenever a bit in num1 is set, set the same bit in x while you still have remaining bits to place. This keeps the high-value bits aligned and minimizes the XOR contribution. If there are still bits left after this pass, fill them starting from the least significant positions where x currently has 0. This greedy ordering ensures minimal XOR while maintaining the required bit count. The algorithm processes a fixed number of bits (typically 32), so the time complexity is effectively constant.
The strategy works because higher bits contribute more to the XOR value. Matching them first avoids large penalties. Lower bits are used later to satisfy the remaining bit count with minimal impact. This is a classic greedy choice using properties of bit manipulation and bit significance.
Approach 2: Dynamic Bit Position Filling (O(log M) time, O(1) space)
This variation treats the problem as filling bit positions dynamically based on remaining capacity. First count the set bits in num2. Traverse the bits of num1 from the highest bit downward and copy matching set bits into x while decrementing the remaining count. After the first pass, iterate again from the least significant bit upward and place additional bits wherever x currently has 0 until the required count is reached.
Unlike the strict greedy framing, this version separates the matching phase and the filling phase more explicitly. It makes the implementation easier to reason about during interviews because each loop has a single responsibility: first minimize XOR by alignment, then satisfy the remaining bit constraint. The number of iterations depends on the bit length of the integers, which is O(log M) for maximum value M.
Both approaches rely on counting bits and manipulating individual positions, which are common patterns in greedy algorithms and bit manipulation problems.
Recommended for interviews: The greedy bit setting strategy is what most interviewers expect. It shows you understand how XOR magnitude depends on bit significance and how to apply a greedy choice to minimize it. Mentioning the two-phase process (match high bits first, then fill low bits) demonstrates strong control over bit-level reasoning.
Approach 1: Greedy Bit Setting Strategy
To minimize the XOR between x and num1, we want to align the 1s in x with the 0s in num1 as much as possible. This way, we reduce the number of bits where x and num1 differ.
The approach involves counting the number of set bits in num2 (let's call it countSetBitsNum2). Then, we construct the integer x by iteratively setting the least significant unset bits of num1 to 1 until x has countSetBitsNum2 set bits.
def minimizeXOR(num1, num2):
countSetBitsNum2 = bin(num2).count('1')
x = 0
availableBits = countSetBitsNum2
for i in range(32):
if (availableBits > 0) and ((num1 & (1 << i)) == 0):
x |= (1 << i)
availableBits -= 1
for i in range(32):
if availableBits > 0 and ((x & (1 << i)) == 0):
x |= (1 << i)
availableBits -= 1
return x
# Test case
def main():
num1 = 3
num2 = 5
print(minimizeXOR(num1, num2)) # Output: 3
main()public class MinimizeXOR {
public static int minimizeXOR(int num1, int num2) {
int countSetBitsNum2 = Integer.bitCount(num2);
int x = 0;
int availableBits = countSetBitsNum2;
for (int i = 0; i < 32 && availableBits > 0; i++) {
if ((num1 & (1 << i)) == 0) {
x |= (1 << i);
availableBits--;
}
}
for (int i = 0; i < 32 && availableBits > 0; i++) {
if ((x & (1 << i)) == 0) {
x |= (1 << i);
availableBits--;
}
}
return x;
}
public static void main(String[] args) {
int num1 = 3, num2 = 5;
System.out.println(minimizeXOR(num1, num2)); // Output: 3
}
}#include <iostream>
int minimizeXOR(int num1, int num2) {
int countSetBitsNum2 = __builtin_popcount(num2);
int x = 0;
int availableBits = countSetBitsNum2;
// First try to set bits in x where num1 has unset bits
for (int i = 0; i < 32 && availableBits > 0; i++) {
if ((num1 & (1 << i)) == 0) {
x |= (1 << i);
availableBits--;
}
}
// Now set remaining bits from the lowest bit until availableBits are zero
for (int i = 0; i < 32 && availableBits > 0; i++) {
if ((x & (1 << i)) == 0) {
x |= (1 << i);
availableBits--;
}
}
return x;
}
int main() {
int num1 = 3, num2 = 5;
std::cout << minimizeXOR(num1, num2) << std::endl; // Output: 3
return 0;
}function minimizeXOR(num1, num2) {
const countSetBitsNum2 = num2.toString(2).split('1').length - 1;
let x = 0;
let availableBits = countSetBitsNum2;
for (let i = 0; i < 32 && availableBits > 0; i++) {
if ((num1 & (1 << i)) === 0) {
x |= (1 << i);
availableBits--;
}
}
for (let i = 0; i < 32 && availableBits > 0; i++) {
if ((x & (1 << i)) === 0) {
x |= (1 << i);
availableBits--;
}
}
return x;
}
// Test
console.log(minimizeXOR(3, 5)); // Output: 3#include <stdio.h>
int minimizeXOR(int num1, int num2) {
int countSetBitsNum2 = __builtin_popcount(num2);
int x = 0;
int availableBits = countSetBitsNum2;
// First try to set bits in x where num1 has unset bits
for (int i = 0; i < 32 && availableBits > 0; i++) {
if ((num1 & (1 << i)) == 0) {
x |= (1 << i);
availableBits--;
}
}
// Now set remaining bits from the lowest bit until availableBits are zero
for (int i = 0; i < 32 && availableBits > 0; i++) {
if ((x & (1 << i)) == 0) {
x |= (1 << i);
availableBits--;
}
}
return x;
}
int main() {
int num1 = 3, num2 = 5;
printf("%d\n", minimizeXOR(num1, num2)); // Output: 3
return 0;
}public class MinimizeXOR {
public static int MinimizeXOR(int num1, int num2) {
int countSetBitsNum2 = CountBits(num2);
int x = 0;
int availableBits = countSetBitsNum2;
for (int i = 0; i < 32 && availableBits > 0; i++) {
if ((num1 & (1 << i)) == 0) {
x |= (1 << i);
availableBits--;
}
}
for (int i = 0; i < 32 && availableBits > 0; i++) {
if ((x & (1 << i)) == 0) {
x |= (1 << i);
availableBits--;
}
}
return x;
}
private static int CountBits(int num) {
int count = 0;
while (num > 0) {
count += num & 1;
num >>= 1;
}
return count;
}
public static void Main(string[] args) {
Console.WriteLine(MinimizeXOR(3, 5)); // Output: 3
}
}In Python, the function uses bin(num2).count('1') to count set bits of num2. The rest of the logic similarly aims to minimize the difference (XOR value) by aligning unset bit positions of num1 with 1's.
Time Complexity: O(32) = O(1), a constant number of binary operations.
Space Complexity: O(1) without extra data structures.
Approach 2: Dynamic Bit Position Filling
This alternative approach validates a typical bit manipulation strategy: setting the most significant unset bits first for minimal overlap in the XOR operation with num1. By setting high bits first, you maximize the influence of remaining unset bits lower than set bits in num1. This can be advantageous depending on the bit composition of num1.
Essentially, the solution is divided into two phases: one filling high bits and a secondary pass correcting any unnecessary zero overlaps if num1 still has unset bits available.
def minimizeXOR(num1, num2):
countSetBitsNum2 = bin(num2).count('1')
x = 0
for i in range(31, -1, -1):
if countSetBitsNum2 > 0 and (num1 & (1 << i)) == 0:
x |= (1 << i)
countSetBitsNum2 -= 1
for i in range(32):
if countSetBitsNum2 > 0 and (x & (1 << i)) == 0:
x |= (1 << i)
countSetBitsNum2 -= 1
return x
# Test
def main():
num1 = 3
num2 = 5
print(minimizeXOR(num1, num2)) # Output: 3
main()public class MinimizeXOR {
public static int minimizeXOR(int num1, int num2) {
int countSetBitsNum2 = Integer.bitCount(num2);
int x = 0;
for (int i = 31; i >= 0 && countSetBitsNum2 > 0; i--) {
if ((num1 & (1 << i)) == 0) {
x |= (1 << i);
countSetBitsNum2--;
}
}
for (int i = 0; i < 32 && countSetBitsNum2 > 0; i++) {
if ((x & (1 << i)) == 0) {
x |= (1 << i);
countSetBitsNum2--;
}
}
return x;
}
public static void main(String[] args) {
int num1 = 3, num2 = 5;
System.out.println(minimizeXOR(num1, num2)); // Output: 3
}
}#include <iostream>
int minimizeXOR(int num1, int num2) {
int countSetBitsNum2 = __builtin_popcount(num2);
int x = 0;
for (int i = 31; i >= 0 && countSetBitsNum2 > 0; i--) {
if ((num1 & (1 << i)) == 0) {
x |= (1 << i);
countSetBitsNum2--;
}
}
for (int i = 0; i < 32 && countSetBitsNum2 > 0; i++) {
if ((x & (1 << i)) == 0) {
x |= (1 << i);
countSetBitsNum2--;
}
}
return x;
}
int main() {
int num1 = 3, num2 = 5;
std::cout << minimizeXOR(num1, num2) << std::endl; // Output: 3
return 0;
}function minimizeXOR(num1, num2) {
const countSetBitsNum2 = num2.toString(2).split('1').length - 1;
let x = 0;
for (let i = 31; i >= 0 && countSetBitsNum2 > 0; i--) {
if ((num1 & (1 << i)) === 0) {
x |= (1 << i);
countSetBitsNum2--;
}
}
for (let i = 0; i < 32 && countSetBitsNum2 > 0; i++) {
if ((x & (1 << i)) === 0) {
x |= (1 << i);
countSetBitsNum2--;
}
}
return x;
}
// Test
console.log(minimizeXOR(3, 5)); // Output: 3#include <stdio.h>
int minimizeXOR(int num1, int num2) {
int countSetBitsNum2 = __builtin_popcount(num2);
int x = 0;
// Fill 'x' with 1-bits starting from most significant to least significant
for (int i = 31; i >= 0 && countSetBitsNum2 > 0; i--) {
if ((num1 & (1 << i)) == 0) {
x |= (1 << i);
countSetBitsNum2--;
}
}
// Fill remaining bits if there are more needed
for (int i = 0; i < 32 && countSetBitsNum2 > 0; i++) {
if ((x & (1 << i)) == 0) {
x |= (1 << i);
countSetBitsNum2--;
}
}
return x;
}
int main() {
int num1 = 3, num2 = 5;
printf("%d\n", minimizeXOR(num1, num2)); // Output: 3
return 0;
}public class MinimizeXOR {
public static int MinimizeXOR(int num1, int num2) {
int countSetBitsNum2 = CountBits(num2);
int x = 0;
for (int i = 31; i >= 0 && countSetBitsNum2 > 0; i--) {
if ((num1 & (1 << i)) == 0) {
x |= (1 << i);
countSetBitsNum2--;
}
}
for (int i = 0; i < 32 && countSetBitsNum2 > 0; i++) {
if ((x & (1 << i)) == 0) {
x |= (1 << i);
countSetBitsNum2--;
}
}
return x;
}
private static int CountBits(int num) {
int count = 0;
while (num > 0) {
count += num & 1;
num >>= 1;
}
return count;
}
public static void Main(string[] args) {
Console.WriteLine(MinimizeXOR(3, 5)); // Output: 3
}
}The Python solution follows the same bitwise filling process, exploring bit significance from the most impactful down to the most minor, duly emulated by sequential loop constructs and styled through Pythonic ways of bit manipulation.
Time Complexity: O(32) = O(1) due to iterations over a fixed-size data type.
Space Complexity: O(1) fixed space consumption from immutable integer operations.
Approach 3: Greedy + Bit Manipulation
According to the problem description, we first calculate the number of set bits in num2, denoted as cnt. Then, we iterate from the highest to the lowest bit of num1; if the current bit is 1, we set the corresponding bit in x to 1 and decrement cnt, until cnt becomes 0. If cnt is still not 0, we iterate from the lowest bit upwards, setting positions where num1 has 0 to 1 in x, and decrement cnt until it reaches 0.
The time complexity is O(log n), where n is the maximum value of num1 and num2. The space complexity is O(1).
function minimizeXor(num1: number, num2: number): number {
let cnt = 0;
while (num2) {
num2 &= num2 - 1;
++cnt;
}
let x = 0;
for (let i = 30; i >= 0 && cnt > 0; --i) {
if ((num1 >> i) & 1) {
x |= 1 << i;
--cnt;
}
}
for (let i = 0; cnt > 0; ++i) {
if (!((num1 >> i) & 1)) {
x |= 1 << i;
--cnt;
}
}
return x;
}func minimizeXor(num1 int, num2 int) int {
cnt := bits.OnesCount(uint(num2))
x := 0
for i := 30; i >= 0 && cnt > 0; i-- {
if num1>>i&1 == 1 {
x |= 1 << i
cnt--
}
}
for i := 0; cnt > 0; i++ {
if num1>>i&1 == 0 {
x |= 1 << i
cnt--
}
}
return x
}impl Solution {
pub fn minimize_xor(num1: i32, mut num2: i32) -> i32 {
let mut cnt = 0;
while num2 > 0 {
num2 -= num2 & -num2;
cnt += 1;
}
let mut x = 0;
let mut c = cnt;
for i in (0..=30).rev() {
if c > 0 && (num1 >> i) & 1 == 1 {
x |= 1 << i;
c -= 1;
}
}
for i in 0..=30 {
if c == 0 {
break;
}
if ((num1 >> i) & 1) == 0 {
x |= 1 << i;
c -= 1;
}
}
x
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Bit Setting Strategy | Time Complexity: O(32) = O(1), a constant number of binary operations. |
| Dynamic Bit Position Filling | Time Complexity: O(32) = O(1) due to iterations over a fixed-size data type. |
| Greedy + Bit Manipulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Bit Setting Strategy | O(1) | O(1) | Best general solution. Minimizes XOR by matching high bits first. |
| Dynamic Bit Position Filling | O(log M) | O(1) | Useful when explaining the logic in two clear phases during interviews. |
Frequently asked questions
Is Minimize XOR easy or hard?
Minimize XOR is generally rated Medium difficulty. The implementation is short, but the key insight is understanding how XOR magnitude depends on bit positions and why matching higher bits first leads to the optimal result.
Minimize XOR Python/Java solution
Python and Java implementations follow the same idea: count the set bits in num2, iterate through the bits of num1 from most significant to least significant, and build the result integer greedily. If more bits are required, set them starting from the least significant positions.
How to solve Minimize XOR in O(n)?
The problem is typically solved in O(log M) or constant time rather than O(n). Count the set bits in num2, then greedily copy matching set bits from num1 starting from the most significant position. If more bits are needed, fill them from the least significant positions until the count matches.
What is the best approach for Minimize XOR?
The greedy bit setting strategy is the most efficient approach. It first matches the highest set bits of num1 to reduce XOR impact, then fills remaining bits from the least significant positions. This guarantees the smallest possible XOR while maintaining the required number of set bits. The runtime is effectively O(1) since integers have a fixed bit width.
Is Minimize XOR asked at Google/Amazon/Meta?
Bit manipulation and greedy reasoning problems like Minimize XOR commonly appear in interviews at companies such as Google, Amazon, and Meta. Variants often test understanding of bit significance, popcount operations, and constructing numbers with constraints.
What data structure is used in Minimize XOR?
No complex data structures are required. The solution mainly uses bit manipulation operations such as bit shifting, masking, and counting set bits. The algorithm works directly on integer bit representations.
What is the time complexity of Minimize XOR?
The optimal solution runs in O(1) time with O(1) space because it processes a fixed number of bits (typically 32 or 64 depending on the integer type). Even when expressed as O(log M), where M is the maximum integer value, the complexity remains very small in practice.