Problem Description

You are given two positive integers num1 and num2. Your task is to find a positive integer x that satisfies two conditions:

1. The integer x must have the exact same number of set bits (1s in binary representation) as num2
2. The XOR operation between x and num1 should produce the smallest possible result

The XOR operation compares bits at each position - it returns 1 when bits are different and 0 when they are the same.

For example, if num1 = 3 (binary: 11) and num2 = 5 (binary: 101), then num2 has 2 set bits. We need to find an integer x with exactly 2 set bits such that x XOR num1 is minimized.

To minimize x XOR num1, we want x to be as similar to num1 as possible. The strategy is:

• First, try to match the 1-bits in num1 by setting those same positions to 1 in x (this makes those positions become 0 after XOR)
• If we still need more set bits to match the count from num2, add 1s in positions where num1 has 0s, starting from the least significant positions

The problem guarantees that there is a unique solution for each test case.

Intuition

To minimize x XOR num1, we need to understand what XOR does - it produces 0 when bits match and 1 when they differ. So to get the smallest XOR result, we want as many 0s as possible in the result, especially in the higher bit positions (since they contribute more to the final value).

The key insight is that we get a 0 in the XOR result when x and num1 have the same bit value at that position. Since we want to minimize the XOR result, we should prioritize matching the higher-order bits of num1 first.

Here's the greedy strategy:

1. Match the 1-bits from high to low: Start from the most significant bits of num1. Wherever num1 has a 1, we should also put a 1 in x at that position (if we still have set bits to use). This ensures these positions become 0 after XOR, contributing nothing to the result.

2. Handle remaining set bits: If we've matched all the 1s in num1 but still need more set bits to reach our target count (from num2), we must add 1s where num1 has 0s. To minimize impact, we add these from the least significant positions upward, since lower bits contribute less to the final value.

For example, if num1 = 1100 (binary) and we need 3 set bits total:

• First, match the two 1s in num1: x becomes 1100 (used 2 set bits)
• Still need 1 more set bit, so add it at the lowest available 0 position: x becomes 1101
• 1100 XOR 1101 = 0001, which is minimal

This greedy approach works because placing 1s where num1 already has 1s "cancels them out" in XOR, while any additional 1s we're forced to add should be in the least significant positions to minimize their contribution.

Learn more about Greedy patterns.

Solution Approach

The implementation follows the greedy strategy we identified, using bit manipulation to efficiently construct the result:

Step 1: Count the required set bits

cnt = num2.bit_count()

We first determine how many 1-bits we need in our answer x by counting the set bits in num2.

Step 2: Match 1-bits from high to low

x = 0
for i in range(30, -1, -1):
    if num1 >> i & 1 and cnt:
        x |= 1 << i
        cnt -= 1

We iterate through bit positions from 30 down to 0 (covering all bits in a 32-bit integer). For each position i:

• num1 >> i & 1 checks if bit i of num1 is 1
• If it is 1 and we still have set bits to place (cnt > 0), we set bit i in x using x |= 1 << i
• We decrement cnt after placing each bit

This ensures we first match all the 1-bits in num1 from most significant to least significant, minimizing the higher-order bits in the XOR result.

Step 3: Place remaining bits in 0 positions

for i in range(30):
    if num1 >> i & 1 ^ 1 and cnt:
        x |= 1 << i
        cnt -= 1

If we still need more set bits after matching all 1s in num1, we iterate from bit 0 upward:

• num1 >> i & 1 ^ 1 checks if bit i of num1 is 0 (using XOR with 1 to flip the bit check)
• If it's 0 and we still need set bits (cnt > 0), we set bit i in x
• We decrement cnt for each bit placed

This places any remaining required 1-bits in the lowest available positions where num1 has 0s, minimizing their contribution to the final XOR value.

The algorithm runs in O(1) time since we iterate through at most 31 bits twice, and uses O(1) space to store the result.

Example Walkthrough

Let's walk through an example with num1 = 11 (binary: 1011) and num2 = 13 (binary: 1101).

Step 1: Count required set bits

• num2 = 13 has binary representation 1101
• Count of set bits = 3
• So we need to construct x with exactly 3 set bits

Step 2: Match 1-bits from high to low in num1

• num1 = 11 has binary representation 1011
• Scanning from high to low (bit positions 30 down to 0):
  • Bit 3: num1 has 1 → set bit 3 in x, now x = 1000, cnt = 2
  • Bit 2: num1 has 0 → skip
  • Bit 1: num1 has 1 → set bit 1 in x, now x = 1010, cnt = 1
  • Bit 0: num1 has 1 → set bit 0 in x, now x = 1011, cnt = 0

Step 3: Place remaining bits (if any)

• We've used all 3 required bits, so cnt = 0
• No additional bits needed

Result:

• x = 1011 (decimal: 11)
• x XOR num1 = 1011 XOR 1011 = 0000 = 0

The XOR result is 0, which is the minimum possible value. This makes sense because we had enough set bits in num1 (3 bits) to match our requirement exactly.

Another example: num1 = 3 (binary: 11) and num2 = 5 (binary: 101)

Step 1: num2 has 2 set bits, so we need exactly 2 set bits in x

Step 2: Match 1-bits in num1 from high to low:

• Bit 1: num1 has 1 → set bit 1 in x, now x = 10, cnt = 1
• Bit 0: num1 has 1 → set bit 0 in x, now x = 11, cnt = 0

Step 3: cnt = 0, no additional bits needed

Result: x = 11 (decimal: 3), and 3 XOR 3 = 0

Example with remaining bits: num1 = 4 (binary: 100) and num2 = 7 (binary: 111)

Step 1: num2 has 3 set bits

Step 2: Match 1-bits in num1:

• Bit 2: num1 has 1 → set bit 2 in x, now x = 100, cnt = 2

Step 3: Still need 2 more bits, add from lowest 0-positions:

• Bit 0: num1 has 0 → set bit 0 in x, now x = 101, cnt = 1
• Bit 1: num1 has 0 → set bit 1 in x, now x = 111, cnt = 0

Result: x = 111 (decimal: 7), and 100 XOR 111 = 011 = 3

Solution Implementation

Time and Space Complexity

The time complexity is O(log n), where n is the maximum value of num1 and num2. This is because:

• The first loop iterates from bit position 30 down to 0, which is O(31) = O(1) iterations in terms of constant operations, but represents O(log n) in terms of the number of bits needed to represent the maximum value n
• The second loop iterates from bit position 0 to 29, which similarly is O(30) = O(1) constant iterations, but represents O(log n) bit positions
• The bit_count() operation on num2 also takes O(log n) time as it needs to count set bits in the binary representation
• Each iteration performs constant time operations: bit shifting (>>), bitwise AND (&), bitwise OR (|), and bitwise XOR (^)

The space complexity is O(1) because:

• Only a fixed number of integer variables are used: cnt and x
• The loop variable i also uses constant space
• No additional data structures that grow with input size are created
• All operations are performed in-place using bitwise operations

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Bit Range or Off-by-One Errors

A common mistake is using an incorrect range for bit positions. Since the problem states positive integers and typical constraints go up to 10^9 (which requires 30 bits), using range(31) or range(32) might seem correct, but could lead to issues:

Pitfall Example:

# Incorrect: might check unnecessary bits
for i in range(31, -1, -1):  # Checking bit 31 when not needed
    if num1 >> i & 1 and cnt:
        x |= 1 << i
        cnt -= 1

Solution: Determine the actual bit range needed. For most problems with constraint up to 10^9, 30 bits suffice:

# Correct: Check only necessary bits (0-29 for numbers up to 10^9)
for i in range(30, -1, -1):
    if num1 >> i & 1 and cnt:
        x |= 1 << i
        cnt -= 1

2. Operator Precedence Confusion

Bitwise operators have lower precedence than comparison operators, which can cause unexpected behavior:

Pitfall Example:

# Incorrect: This evaluates as (num1 >> i) & (1 and cnt)
if num1 >> i & 1 and cnt:  # Works but unclear
    x |= 1 << i
  
# Even worse: forgetting parentheses in XOR check
if num1 >> i & 1 ^ 1 and cnt:  # XOR has lower precedence than &

Solution: Use parentheses for clarity and correctness:

# Clear and correct
if ((num1 >> i) & 1) and cnt > 0:
    x |= 1 << i
    cnt -= 1

# For checking if bit is 0
if ((num1 >> i) & 1) == 0 and cnt > 0:
    x |= 1 << i
    cnt -= 1

3. Not Handling Edge Cases

Failing to consider when num2 has more or fewer set bits than num1:

Pitfall Example:

# Might not work if num2.bit_count() > num1.bit_count()
# Only tries to match existing 1s in num1
for i in range(30, -1, -1):
    if num1 >> i & 1:
        x |= 1 << i
# Forgets to add remaining bits in 0 positions

Solution: Always implement both phases - matching 1s and adding to 0s:

cnt = num2.bit_count()
x = 0

# Phase 1: Match 1s in num1
for i in range(30, -1, -1):
    if (num1 >> i) & 1 and cnt > 0:
        x |= 1 << i
        cnt -= 1

# Phase 2: Add remaining bits to 0 positions
for i in range(30):
    if ((num1 >> i) & 1) == 0 and cnt > 0:
        x |= 1 << i
        cnt -= 1

4. Using Wrong Direction in Second Pass

Setting bits in the wrong order when adding to 0 positions:

Pitfall Example:

# Incorrect: Adding from MSB to LSB in second pass
for i in range(30, -1, -1):  # Wrong direction!
    if ((num1 >> i) & 1) == 0 and cnt > 0:
        x |= 1 << i
        cnt -= 1

Solution: Add remaining bits from LSB to MSB to minimize the XOR value:

# Correct: Add from LSB (0) to MSB (29)
for i in range(30):
    if ((num1 >> i) & 1) == 0 and cnt > 0:
        x |= 1 << i
        cnt -= 1

This ensures that any additional 1s contribute the smallest possible values to the XOR result.