Thomas Ngo

Software Engineer

3 minute read

Problem Statement

problem

Intuition

The problem is to construct a number that has the same number of set bits (1s) as num2, while minimizing the XOR result with num1.

The key observation is that XOR minimizes when the constructed number (res) has its bits as close as possible to num1. To achieve this, prioritize setting the most significant bits of num1 in res while respecting the number of set bits required.

Approach

  1. Count the set bits in num2:

    • Use bitwise operations to calculate the number of 1s in num2 (set_bit).

  2. Identify the leftmost bit position in num1:

    • Iterate through the bits of num1 to find its most significant bit.

  3. Construct the result:

    • Start with res = 0 and try to set bits in res from most significant to least significant:
      • Use the bits of num1 when they are set.
      • Stop setting bits from num1 when the required number of set bits (set_bit) is satisfied.
    • If additional bits need to be set after using all possible bits from num1, set the least significant bits in res.

  4. Return the result:

    • The constructed number (res) minimizes the XOR value with num1 and satisfies the set bit condition.

Complexity

  • Time Complexity:
    \(O(\log(\text{max}(num1, num2)))\)

    • Counting set bits and iterating through bits of num1 are logarithmic in the value of the number.

  • Space Complexity:
    \(O(1)\)

    • No additional data structures are used; the space usage is constant.

Code

class Solution:
    def minimizeXor(self, num1: int, num2: int) -> int:
        res = 0
        set_bit = 0
        x, y = num1, num2

        # Count the number of set bits in num2
        while y > 0:
            set_bit += (y & 1)
            y = y >> 1

        # Find the leftmost bit of num1
        left_most_bit_num1 = 1
        while x > 1:
            x = x >> 1
            left_most_bit_num1 = left_most_bit_num1 << 1

        # Set bits in res using num1's bits
        res = 0
        while set_bit > 0 and left_most_bit_num1 > 0:
            if left_most_bit_num1 & num1 == left_most_bit_num1:
                res = res | left_most_bit_num1
                set_bit -= 1
            left_most_bit_num1 = left_most_bit_num1 >> 1

        # Set remaining bits from the least significant position
        curr = 1
        while set_bit > 0:
            if res & curr != curr:
                res = res | curr
                set_bit -= 1
            curr = curr << 1

        return res

Editorial

Trick

To check if the i-th bit of num is set:

Shift 1 left by i (1 << i) positions to isolate the i-th bit.
Perform a bitwise AND: num & (1 << i).
If the result is not 0, the i-th bit of num is set.

----------------------------------------------------------

To set the i-th bit of num:

Shift 1 left by i (1 << i) positions to isolate the i-th bit.
Perfom a bitwise OR: num | (1 << i).

----------------------------------------------------------

To unset the i-th bit of num:

Shift 1 left by i (1 << i) positions to create a mask.
Invert the mask using ~(1 << i) to make the i-th bit 1 and all the other bits 0.
Perform a bitwise AND: num & ~(1 << i).

Approach 1: From Optimal to Valid

class Solution:
    def minimizeXor(self, num1: int, num2: int) -> int:
        # Initialize result to num1. We will modify result.
        result = num1

        target_set_bits_count = bin(num2).count("1")
        set_bits_count = bin(result).count("1")

        # Start with the least significant bit (bit 0).
        current_bit = 0

        # Add bits to result if it has fewer set bits than the target.
        while set_bits_count < target_set_bits_count:
            # If the current bit in result is not set (0), set it to 1.
            if not self._is_set(result, current_bit):
                result = self._set_bit(result, current_bit)
                set_bits_count += 1
            # Move to the next bit.
            current_bit += 1

        # Remove bits from result if it has more set bits than the target.
        while set_bits_count > target_set_bits_count:
            # If the current bit in result is set (1), unset it (make it 0).
            if self._is_set(result, current_bit):
                result = self._unset_bit(result, current_bit)
                set_bits_count -= 1
            # Move to the next bit.
            current_bit += 1

        return result

    # Helper function to check if the given bit position in result is set (1).
    def _is_set(self, x: int, bit: int) -> bool:
        return (x & (1 << bit)) != 0

    # Helper function to set the given bit position in result to 1.
    def _set_bit(self, x: int, bit: int):
        return x | (1 << bit)

    # Helper function to unset the given bit position in x (set it to 0).
    def _unset_bit(self, x: int, bit: int):
        return x & ~(1 << bit)

You may also enjoy