LeetCode 2429 - Minimize XOR

The problem is asking us to construct an integer x that satisfies two conditions. First, x must have the same number of set bits (1's in the binary representation) as a given integer num2. Second, the XOR of x with another integer num1 must be minimized.

leetcodemediumgreedybit-manipulation

LeetCode Problem 2429

Difficulty: 🟡 Medium
Topics: Greedy, Bit Manipulation

Solution

Problem Understanding

The problem is asking us to construct an integer x that satisfies two conditions. First, x must have the same number of set bits (1's in the binary representation) as a given integer num2. Second, the XOR of x with another integer num1 must be minimized. In other words, we want x XOR num1 to be as small as possible, which is equivalent to making x as close to num1 as possible in binary terms, but respecting the constraint on the number of set bits.

The inputs num1 and num2 are positive integers within the range [1, 10^9]. This implies that the maximum number of bits we need to consider is 30, since 2^30 is slightly larger than 10^9. The problem guarantees that the solution is unique, so we do not need to consider ties or multiple possible values of x.

Important edge cases include when num1 and num2 have the same number of set bits (then x = num1), when num2 has more set bits than num1 (we need to add bits), and when num2 has fewer set bits than num1 (we need to remove bits). Handling these carefully ensures the minimal XOR value.

Approaches

The brute-force approach would involve generating all integers that have the same number of set bits as num2 and computing x XOR num1 for each candidate. We would then select the integer with the minimum XOR. While this guarantees correctness, it is computationally infeasible. The number of integers with k set bits in a 30-bit space is C(30, k), which can be very large and would lead to combinatorial explosion.

The optimal approach leverages a greedy bit manipulation strategy. The key insight is that to minimize XOR with num1, we should try to align the set bits of x with the set bits of num1. This can be done in two steps: first, preserve as many set bits in num1 as possible, and second, if we still need more set bits, turn on the lowest unset bits. Conversely, if we need fewer set bits, we turn off the highest set bits. This ensures that x is the closest integer to num1 in terms of XOR while meeting the set bit requirement.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(1) Enumerates all numbers with same set bits as num2, infeasible for n ~ 30
Optimal O(30) O(1) Greedily set/unset bits based on num1 to match num2's set bit count

Algorithm Walkthrough

  1. Count the number of set bits in num2 and store it in target_bits. This is the number of 1's x must have.
  2. Count the number of set bits in num1 and store it in num1_bits.
  3. If num1_bits equals target_bits, then x = num1 and we are done.
  4. If num1_bits is greater than target_bits, we need to turn off some bits in num1. Start from the least significant bit (LSB) and turn off 1's until we reach the required number of set bits.
  5. If num1_bits is less than target_bits, we need to turn on additional bits. Start from the least significant bit and turn on 0's until x has the required number of set bits.
  6. Return the resulting integer x.

Why it works: By aligning the most significant bits of x with num1 as much as possible, we minimize XOR. If additional bits are needed, choosing the lowest unset bits ensures minimal increase in the XOR value. This greedy approach guarantees the XOR is minimized while satisfying the set bit count.

Python Solution

class Solution:
    def minimizeXor(self, num1: int, num2: int) -> int:
        target_bits = bin(num2).count('1')
        num1_bits = bin(num1).count('1')
        x = num1
        
        if num1_bits > target_bits:
            excess = num1_bits - target_bits
            for i in range(31):
                if excess == 0:
                    break
                if (x >> i) & 1:
                    x ^= (1 << i)
                    excess -= 1
        elif num1_bits < target_bits:
            deficit = target_bits - num1_bits
            for i in range(31):
                if deficit == 0:
                    break
                if not ((x >> i) & 1):
                    x |= (1 << i)
                    deficit -= 1
        return x

This Python implementation counts set bits, compares the counts, and either removes or adds bits to match the target. It uses bitwise shifts and masks to manipulate individual bits efficiently. The loops are limited to 31 iterations due to the maximum 30-bit representation of num1 and num2.

Go Solution

func minimizeXor(num1 int, num2 int) int {
    targetBits := 0
    n := num2
    for n > 0 {
        targetBits += n & 1
        n >>= 1
    }
    
    x := num1
    num1Bits := 0
    n = num1
    for n > 0 {
        num1Bits += n & 1
        n >>= 1
    }
    
    if num1Bits > targetBits {
        excess := num1Bits - targetBits
        for i := 0; i < 31; i++ {
            if excess == 0 {
                break
            }
            if (x>>i)&1 == 1 {
                x ^= 1 << i
                excess--
            }
        }
    } else if num1Bits < targetBits {
        deficit := targetBits - num1Bits
        for i := 0; i < 31; i++ {
            if deficit == 0 {
                break
            }
            if (x>>i)&1 == 0 {
                x |= 1 << i
                deficit--
            }
        }
    }
    
    return x
}

The Go implementation follows the same logic as Python, with explicit loops to count bits and manipulate individual bits using bitwise operators.

Worked Examples

Example 1: num1 = 3, num2 = 5

Binary representations: num1 = 0011, num2 = 0101.

target_bits = 2 (num2), num1_bits = 2. Since counts are equal, x = num1 = 3.

Example 2: num1 = 1, num2 = 12

Binary representations: num1 = 0001, num2 = 1100.

target_bits = 2 (num2), num1_bits = 1. Need to add 1 bit. Start from LSB, bit 1 is 0 → set it. Resulting x = 0011 = 3.

Complexity Analysis

Measure Complexity Explanation
Time O(30) Loops over at most 31 bits for counting and manipulation
Space O(1) Only integer variables are used, no extra data structures

The approach is extremely efficient because we only iterate over the fixed bit width of the input integers, not over their magnitude.

Test Cases

# Provided examples
assert Solution().minimizeXor(3, 5) == 3  # same number of bits
assert Solution().minimizeXor(1, 12) == 3  # need to add a bit

# Boundary and edge cases
assert Solution().minimizeXor(1, 1) == 1  # single bit, minimal XOR
assert Solution().minimizeXor(0, 1) == 1  # num1=0, need to add 1 bit
assert Solution().minimizeXor(15, 1) == 8  # num1 has 4 bits, num2 has 1 bit
assert Solution().minimizeXor(8, 15) == 15  # num1=1000, num2=1111, need to add 3 bits
Test Why
3, 5 num1 already matches num2 in set bits
1, 12 num1 has fewer bits than num2, need to add bits
1, 1 minimal input, 1 bit
0, 1 num1 zero, need to add 1 bit
15, 1 num1 has excess bits, need to remove
8, 15 num1 has fewer bits, need to add multiple bits

Edge Cases

One edge case is when num1 and num2 already have the same number of set bits. A naive implementation might try to change bits unnecessarily, but the correct approach recognizes this equality and returns num1 immediately.

Another edge case occurs when num1 has more set bits than num2. The algorithm carefully iterates from the least significant bit upward to turn off