[Solved] Minimize XOR LeetCode Contest Problem

Given two positive integers num1 and num2, find the 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.

Minimize XOR LeetCode Contest

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

Solution

Firstly we need to know the number of set bits of num1 and num2.
Let a = bitCount(num1) and b = bitCount(num2).

If a == b, we can pick x = num1 and x XOR num1 = 0 is minimal.

Explanation

If a > b, we can pick x equals the bigger b bits of num1,
so that we can XOR the bigger b bits of num1,
and keep the smaller a - b bits left to make the result small.

If a < b, we can firstly pick x = num1,
and additionally, we need to pick b - a more bits that not in num1.
We check from the smaller bits until x have b bits.

Complexity

Time O(n^2)
Space O(n)

Java

    public int minimizeXor(int num1, int num2) {
        int a = Integer.bitCount(num1), b = Integer.bitCount(num2), res = num1;
        for (int i = 0; i < 32; ++i) {
            if (a > b && ((1 << i) & num1) > 0) {
                res ^= 1 << i;
                b += 1;
            }
            if (a < b && ((1 << i) & num1) == 0) {
                res ^= 1 << i;
                a += 1;
            }
        }
        return res;
    }

C++

    int minimizeXor(int num1, int num2) {
        int a = __builtin_popcount(num1), b = __builtin_popcount(num2), res = num1;
        for (int i = 0; i < 32; ++i) {
            if (a > b && ((1 << i) & num1) > 0) {
                res ^= 1 << i;
                b += 1;
            }
            if (a < b && ((1 << i) & num1) == 0) {
                res ^= 1 << i;
                a += 1;
            }
        }
        return res;
    }

Python

    def minimizeXor(self, num1, num2):
        a, b = num1.bit_count(), num2.bit_count()
        res = num1
        for i in range(32):
            if a > b and (1 << i) & num1 > 0:
                res ^= 1 << i
                b += 1
            if a < b and (1 << i) & num1 == 0:
                res ^= 1 << i
                a += 1
        return res

Happy Learning – If you require any further information, feel free to contact me.