Minimize XOR

2429. Minimize XOR

Difficulty: Medium

Topics: Greedy, Bit Manipulation

This problem challenges you to find a positive integer, x, that meets two conditions: it has the same number of set bits (1s in its binary representation) as a given integer, num2, and its bitwise XOR with another given integer, num1, is minimized.

Example 1:

• Input: num1 = 3, num2 = 5
• Output: 3
• Explanation: 3 (0011) and 5 (0101) both have two set bits. 3 XOR 3 = 0, which is the minimum possible XOR value.

Example 2:

• Input: num1 = 1, num2 = 12
• Output: 3
• Explanation: 12 (1100) has two set bits. 3 (0011) also has two set bits, and 3 XOR 1 = 2.

Constraints:

• 1 ≤ num1, num2 ≤ 10⁹

Solution Approach:

The key is a greedy strategy. To minimize the XOR result, we want to align the set bits of x with the set bits of num1 as much as possible.

1. Count Set Bits: Determine the number of set bits in num2. Let's call this targetBits.

2. Construct x: Initialize x to 0. Iterate through the bits of num1, starting from the most significant bit. For each set bit in num1, if we haven't reached targetBits yet, add that bit to x. If we've already met the targetBits requirement, skip the bit. If we haven't reached targetBits after processing all bits of num1, add the remaining bits to x, starting from the least significant bit.

3. Return x: The constructed x will satisfy the conditions.

PHP Implementation:

<code class="language-php"><?php
function minimizeXor(int $num1, int $num2): int {
    $targetBits = countSetBits($num2);
    $x = 0;
    $bitsSet = 0;

    for ($i = 30; $i >= 0; $i--) {
        if (($num1 >> $i) & 1) { // Check if the i-th bit of num1 is set
            if ($bitsSet < $targetBits) {
                $x |= (1 << $i); // Set the i-th bit of x
                $bitsSet++;
            }
        }
    }

    // If we haven't reached targetBits, add remaining bits from LSB
    for ($i = 0; $i < 31 && $bitsSet < $targetBits; $i++) {
        if (!($x & (1 << $i))) { //check if bit is not set yet
            $x |= (1 << $i);
            $bitsSet++;
        }
    }

    return $x;
}

function countSetBits(int $n): int {
    $count = 0;
    while ($n > 0) {
        $count += $n & 1;
        $n >>= 1;
    }
    return $count;
}

// Test cases
echo minimizeXor(3, 5) . PHP_EOL; // Output: 3
echo minimizeXor(1, 12) . PHP_EOL; // Output: 3
echo minimizeXor(10, 7) . PHP_EOL; //Output: 11
?></code>

Time and Space Complexity:

• Time Complexity: O(log N), where N is the maximum value of num1 and num2. This is because we iterate through the bits of the numbers.
• Space Complexity: O(1), constant extra space is used.

This improved solution provides a clearer, more efficient, and more robust way to solve the problem. The comments explain the logic at each step.

The above is the detailed content of Minimize XOR. For more information, please follow other related articles on the PHP Chinese website!