Today’s problem

https://leetcode.com/problems/minimize-xor/description/

XOR

This is the True-False Diagram for $XOR$: image.png In this diagram, we can find that if A and B is the same, then $A\space XOR\space B = 0$; else, $A\space XOR\space B = 1$.

Intuition

  • For the first requirement in the question, “same number of set bits” means “same number of bit 1 in the number”.

  • Why? This is because the number of 0 in a number can be infinity, while only the number of bit 1 is finite.

  • Therefore, we need to count how many 1s are there in number2.

  • Now, based on the $XOR$ Diagram we know that to make a number after doing $XOR$, we need to put a one in the same position where number1 has a 1, so that we can decrease it to 0 after doing $XOR$.

  • In this case, we want the “decreased” 1s from top to down to minimize the result.

  • If there are more 1s in number2 than number1, we would have to add new 1s to the result.

  • In this case, we want to “add” 1s from down to top to minimize the result.

Approach

  1. Use $bit_count()$ function to count the 1s in num2.
  2. Iterate from top to down to decrease 1.
  3. Iterate from down to top to add 1.

Complexity

  • Time complexity: $O(log_2(N))$, N means the number.

  • Space complexity: $O(1)$, only some variables are stored

Code

class Solution:
    def minimizeXor(self, num1: int, num2: int) -> int:
        cnt,ans = num2.bit_count(), 0
        for i in range(31, -1, -1):
            if cnt > 0 and (num1 & (1 << i)) > 0:
                ans += (1 << i)
                cnt -= 1
        
        for i in range(31):
            if cnt > 0 and (ans & (1 << i)) == 0:
                ans += (1 << i)
                cnt -= 1
        
        return ans

image.png