We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimize XOR

Number: 2509

Difficulty: Medium

Paid? No

Companies: Amazon, Microsoft, Google, Adobe

Problem Description

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

  • x has the same number of set bits (1’s) in its binary representation as num2.
  • The value (x XOR num1) is minimized.

The problem guarantees that there is a unique integer x that satisfies these conditions.

Key Insights

  • To minimize (x XOR num1), x should be as "similar" as possible to num1.
  • Since x must have exactly k set bits (where k = the number of set bits in num2), the best strategy is to retain as many of num1's set bits as possible.
  • If num1 contains more than k set bits, we remove some set bits from num1. To minimize the XOR value, it is best to remove bits with lower significance (i.e. the ones contributing less to the total value).
  • If num1 contains fewer than k set bits, we add additional set bits to positions where num1 has a 0, again choosing the positions with the smallest weights first to keep the XOR difference minimal.
  • This greedy approach, by working with bit positions starting from the least significant bit, ensures minimal contribution in the XOR result for any differences.

Space and Time Complexity

Time Complexity: O(32) ~ O(1) since we only iterate over a fixed number of bit positions. Space Complexity: O(1)

Solution

The solution involves the following steps:

  1. Count the number of set bits (ones) in num2 and num1.
  2. If num1 already has exactly the required number of set bits, return num1.
  3. If num1 has more set bits than required, identify positions where num1 has a 1. Then, from the least significant bit (lowest weight), unset bits until the number of 1’s equals the required count. Removing bits from lower positions minimizes the impact on the XOR value.
  4. If num1 has fewer set bits than required, identify positions where num1 has a 0. Then, set bits (starting from the least significant positions) until the total set bits equals the required count.
  5. Return the resulting integer.

Data structures used: Simple integer bit manipulations and iteration over bit positions (constant 32 iterations). The greedy approach is used to choose bits with lower significance first.

Code Solutions

# Python Solution

def minimizeXor(num1: int, num2: int) -> int:
    # Count the required number of set bits from num2
    target_bits = bin(num2).count("1")
    
    # Count the current number of set bits in num1
    current_bits = bin(num1).count("1")
    
    # If num1 already has the required number of set bits, return num1
    if current_bits == target_bits:
        return num1
    
    # Initialize the answer based on num1
    result = num1
    
    # If there are too many 1s in num1, need to unset some bits.
    if current_bits > target_bits:
        # Process bit positions from least significant bit to most to remove lowest weighted bits first
        for i in range(32):
            # Check if the i-th bit is set
            if result & (1 << i):
                # Unset the bit at position i
                result &= ~(1 << i)
                current_bits -= 1
                # When we have removed enough bits, break out of loop
                if current_bits == target_bits:
                    break
    
    # If there are too few 1s in num1, need to set extra bits.
    elif current_bits < target_bits:
        # Process positions from least significant bit to most
        for i in range(32):
            # If the i-th bit is not set in num1
            if not (num1 & (1 << i)) and not (result & (1 << i)):
                # Set the bit at position i
                result |= (1 << i)
                current_bits += 1
                # When the required count is reached, break out of loop
                if current_bits == target_bits:
                    break
    return result

# Example usage:
print(minimizeXor(3, 5))  # Expected output 3
print(minimizeXor(1, 12)) # Expected output 3
← Back to All Questions