Minimize XOR

Leetcode Problem:

• Minimize XOR

Summary

• 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.

Approach

• The solution uses a two-step approach
• First, it counts the number of set bits in num1 and num2 using a helper function
• Then, it adjusts num1 to have the same number of set bits as num2 by shifting bits to the right and/or left until the difference is zero
• The final result is the adjusted num1.

Complexity

• O(log max(num1, num2))

Explanation

• The time complexity is O(log max(num1, num2)) because in the worst case, we need to shift bits up to 32 places to the right (for a 32-bit integer)
• The space complexity is O(1) because we only use a constant amount of space to store the result and the temporary variables.

Solution Code:

class Solution {
public:
    int bitCount(int n){
        int cnt = 0;
        while(n){
            cnt++;
            n &= n-1;
        }
        return cnt;
    }
    int minimizeXor(int num1, int num2) {
        int bit1 = bitCount(num1);
        int bit2 = bitCount(num2);
        int x = num1;
        int diff = bit2 - bit1;
        if(diff == 0) return num1;
        else if(diff > 0){
            long long offset = 1;
            while(diff){
                if((offset & x) == 0){
                    diff--;
                }
                x |= offset;
                offset <<= 1;
            }
        } else{
            diff = -diff;
            while(diff--){
                x &= x - 1;
            }
        }
        return x;
    }
};