2429. Minimize XOR

Description

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

 

Solutions

Solution: Greedy

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number} num1
 * @param {number} num2
 * @return {number}
 */
const minimizeXor = function (num1, num2) {
  const getBits = binary => {
    let result = 0;

    for (const bit of binary) {
      if (bit === '1') result += 1;
    }
    return result;
  };

  const binary2 = num2.toString(2);
  const targetBits = getBits(binary2);
  let binary1 = num1.toString(2);
  let bits = getBits(binary1);

  if (targetBits === bits) return num1;
  const n = Math.max(binary1.length, binary2.length);

  binary1 = binary1.padStart(n, '0').split('');

  for (let index = n - 1; index >= 0; index--) {
    if (bits < targetBits && binary1[index] === '0') {
      binary1[index] = '1';
      bits += 1;
    }
    if (bits > targetBits && binary1[index] === '1') {
      binary1[index] = '0';
      bits -= 1;
    }
    if (bits === targetBits) return Number.parseInt(binary1.join(''), 2);
  }
  return -1;
};