Daily Leetcode Question 11/09/2024 - 2220. Minimum Bit Flips to Convert Number

Problem Description:

A bit flip of a number x is choosing a bit in the binary representation of x and flipping it from either 0 to 1 or 1 to 0. For example, for x = 7, the binary representation is 111 and we may choose any bit (including any leading zeros not shown) and flip it. We can flip the first bit from the right to get 110, flip the second bit from the right to get 101, flip the fifth bit from the right (a leading zero) to get 10111, etc. Given two integers start and goal, return the minimum number of bit flips to convert start to goal.

class Solution:
  def minBitFlips(self, start: int, goal: int) -> int:
    XOR = start ^ goal
    return bin(XOR).count("1")

Explanation:

We can utilise the XOR operator to solve this.

What XOR does is it finds all the elements that are only in set A and only in set B. That is, in set notations

XOR = |A U B| - |A ∩ B|

So by applying the XOR operation on our two numbers, we can find out how many bits are different. These bits are represented by "1" in the final product. The count will tell us the minimum bit flips required.

def minBitFlips(start, goal):
  XOR = start ^ goal
  return bin(XOR).count("1")

The time complexity is O(1).

The space complexity is O(1).

The full solution can be found near the top of the page.