Problem

Given two positive integers num1 and num2, find the positive integer x such that:

  • x has the same number of set bits as num2, and
  • The value x 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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5

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 <= 10^9

Solution

Method 1 - Count the bits in num2 and minimize xor

Intuition

Given, num1 and num2, we need to find a positive integer x such that 

  1. x has the same number of set bits as num2, i.e. bitCount(x) == bitCount(num2)
  2. x ^ num1 is minimal ⇨ set bits in x should align with those in num1 , i.e. x should have set bits in positions where num1 has 1s as well

If we XOR two bits, the result is 1 if the bits are different but 0 if the bits are the same. For example:

1
2
3
4

0 ^ 0 = 0
1 ^ 1 = 0
0 ^ 1 = 1
1 ^ 0 = 1

So, we want to minimize, hence we try to set the bits at the position, where num1 has set bits as well.

Now, there are 3 cases. Let a = bitCoun(num1) and b = bitCount(num2)(be number of set bits in num2).

Cases

Case 1 - b < a

Suppose, num2 has 3 set bits and num1 can have 5 set bits. So, in x we want to set 3 set bits, and which one should we set? What will have more impact when we perform x ^ num1, when we are nullifying the value, and answer is setting the bits at MSB. So, we will loop from bit position 31 to 0 for that.

Case 2 - b > a Suppose, num2 has 5 set bits and num1 can have 3 set bits. So, in x we want to set 5 set bits. So, we set the 3 bits where num1 has a set bit, and now we still have 2 remaining bits we want to set in x. Where should we set them? And the answer is since we want the minimal answer, we should set them at positions, where they contribute as minimum as possible, i.e. LSB positions, and hence we loop from bit position 0.

Case 3 - b == a

This is the simplest case. Just set the bits as placed in num1.

Approach

  1. Count Set Bits in num2: Calculate the number of set bits (1s) in num2 and store it in cnt. We can use methods described in Number of 1 Bits or use standard library function for that.
  2. Set Common Bits in the Result:
    • To minimize x XOR num1, align set bits of x with those in num1. Iterate from the most significant bit (MSB) to the least significant bit (LSB) of num1:
      • If a bit in num1 is set and cnt is greater than 0, set the corresponding bit in x and decrement cnt.
  3. Set Remaining Bits:
    • If there are still bits left to be set in x (cnt > 0), set them from LSB to MSB:
      • If a bit position in num1 is not set and cnt is greater than 0, set this bit in x and decrement cnt.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public class Solution {
    public int minimizeXor(int num1, int num2) {
        int cnt = Integer.bitCount(num2);
        int ans = 0;
        
        // First pass to set bits where num1 has 1s and decrease cnt
        for (int i = 31; i >= 0; i--) {
            if ((num1 & (1 << i)) != 0) {
                if (cnt > 0) {
                    ans |= (1 << i);
                    cnt--;
                }
            }
        }
        
        // Second pass to set remaining bits to get required number of set bits
        for (int i = 0; i < 32 && cnt > 0; i++) {
            if ((num1 & (1 << i)) == 0) {
                ans |= (1 << i);
                cnt--;
            }
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def minimizeXor(self, num1: int, num2: int) -> int:
        cnt = bin(num2).count('1')
        ans = 0
        
        # Set bits in ans where num1 has bits set, from MSB to LSB
        for i in range(31, -1, -1):
            if (num1 & (1 << i)) != 0 and cnt > 0:
                ans |= (1 << i)
                cnt -= 1
        
        # Set remaining bits in ans from LSB to MSB
        for i in range(32):
            if cnt <= 0:
                break
            if (num1 & (1 << i)) == 0:
                ans |= (1 << i)
                cnt -= 1
        
        return ans

Complexity

  • ⏰ Time complexity: O(1) as we iterate through number of bits from right to left first and left to right later. OR O(log n) if we want to right it in terms of numbers.
  • 🧺 Space complexity: O(1)