2429.MinimizeXOR.md

2429. Minimize XOR

LeetCode Problem Link

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 <= $10^9$

Solution

JavaScript

/**
 * @param {number} num1
 * @param {number} num2
 * @return {number}
 */
var minimizeXor = function(num1, num2) {
    const countOnes = (n) => {
        let count = 0;
        while (n > 0) {
            count++;
            n &= (n - 1);
        }
        return count;
    };

    let num1Bits = countOnes(num1);
    let num2Bits = countOnes(num2);

    if (num1Bits === num2Bits) {
        return num1;
    }

     let result = num1;

    if (num1Bits < num2Bits) {
        for (let i = 0; i < 32 && num1Bits < num2Bits; i++) {
            if (((result >> i) & 1) === 0) {
                result |= (1 << i);
                num1Bits++;
            }
        }
    } else {
        for (let i = 0; i < 32 && num1Bits > num2Bits; i++) {
            if (((result >> i) & 1) === 1) {
                result &= ~(1 << i)
                num1Bits--;
            }
        }
    }

    return result;
};