2429. Minimize XOR

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.

Example 1:

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:

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 <= 109

Approach 01:

class Solution {
public:
    int minimizeXor(int num1, int num2) {
        int setBitsInNum2 = __builtin_popcount(num2);
        int minimizedResult = 0;

        // Set bits in minimizedResult matching bits from num1, starting from MSB
        for (int bit = 31; bit >= 0; --bit) {
            if (setBitsInNum2 == 0) break;
            if (num1 & (1 << bit)) {
                minimizedResult |= (1 << bit);
                --setBitsInNum2;
            }
        }

        // Set remaining bits from LSB to minimize the XOR value
        for (int bit = 0; bit < 32; ++bit) {
            if (setBitsInNum2 == 0) break;
            if (!(minimizedResult & (1 << bit))) {
                minimizedResult |= (1 << bit);
                --setBitsInNum2;
            }
        }

        return minimizedResult;
    }
};

class Solution:
    def minimizeXor(self, num1: int, num2: int) -> int:
        setBitsInNum2 = bin(num2).count('1')
        minimizedResult = 0

        # Set bits in minimizedResult matching bits from num1, starting from MSB
        for bit in range(31, -1, -1):
            if setBitsInNum2 == 0:
                break
            if num1 & (1 << bit):
                minimizedResult |= (1 << bit)
                setBitsInNum2 -= 1

        # Set remaining bits from LSB to minimize the XOR value
        for bit in range(32):
            if setBitsInNum2 == 0:
                break
            if not (minimizedResult & (1 << bit)):
                minimizedResult |= (1 << bit)
                setBitsInNum2 -= 1

        return minimizedResult

Time Complexity:

• First Loop (Setting Bits from num1):

  The loop runs from the most significant bit (31) to the least significant bit (0), iterating at most 32 times. This takes \( O(1) \).

• Second Loop (Setting Remaining Bits):

  The loop runs from the least significant bit (0) to the most significant bit (31), also iterating at most 32 times. This takes \( O(1) \).

• Overall Time Complexity:

  The total time complexity is \( O(1) \).

Space Complexity:

• Variable Usage:

  Only a constant amount of extra space is used for variables like setBitsInNum2, minimizedResult, and loop counters.

• Overall Space Complexity:

  The total space complexity is \( O(1) \).