Minimize XOR - Solution & Explanation
Problem Statement
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.
The solution starts by calculating the number of set bits in num2. Using this count, it tries to place these set bits into the positions of x where num1 has 0s, to minimize the XOR result. If more set bits are needed, it continues filling them in increasing order of significance in x.
Complexity
Time Complexity: O(32) = O(1) due to looping over a fixed number of bits.
Space Complexity: O(1) because we use a constant amount of extra space.
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.
This solution tackles the bit filling in two stages. Initially, it prioritizes setting higher position bits, which doesn't overlap with num1's existing bits. Post this, any remaining lower bits are filled to achieve the correct count of bits set to 1 in x.
Complexity
Time Complexity: O(32) = O(1) for bit processing.
Space Complexity: O(1) based on constant extra space.
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).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Bit Setting Strategy | Time Complexity: O(32) = O(1) due to looping over a fixed number of bits. |
| Dynamic Bit Position Filling | Time Complexity: O(32) = O(1) for bit processing. |
| Greedy + Bit Manipulation | — |
Detailed 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. |
Video Solution
Minimize XOR | 2 Detailed Approaches | Dry Runs | Leetcode 2429 | codestorywithMIK • codestorywithMIK • 11,172 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimize XOR easy or hard?
Minimize XOR Python/Java solution
How to solve Minimize XOR in O(n)?
What is the best approach for Minimize XOR?
Is Minimize XOR asked at Google/Amazon/Meta?
What data structure is used in Minimize XOR?
What is the time complexity of Minimize XOR?
Ready to solve this problem?
Practice Minimize XOR with our built-in code editor and test cases.
Practice on FleetCode