Given two positive integers num1 and num2, find the positive integer x such that:
x has the same number of set bits as num2, andx XOR num1 is 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 <= 109To 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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(32) = O(1) for bit processing.
Space Complexity: O(1) based on constant extra space.
| 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. |
Minimize XOR | 2 Detailed Approaches | Dry Runs | Leetcode 2429 | codestorywithMIK • codestorywithMIK • 9,646 views views
Watch 9 more video solutions →Practice Minimize XOR with our built-in code editor and test cases.
Practice on FleetCode