Thomas Ngo

Software Engineer

2 minute read

Problem Statement

problem

Intuition

The goal is to determine how many bit flips are needed to convert start into goal. The most straightforward way to think about this is by comparing the binary representations of start and goal. For every bit position where the two numbers differ, we will need one flip. The XOR operation gives us exactly this information because it results in a 1 for differing bits and 0 for matching bits.

Approach

We iterate over each bit of both start and goal, comparing the bits at the same position. If the bits differ, we increment a counter. We can compare the least significant bit of each number using the bitwise AND (& 1) operation, and then right shift (>>) both numbers to check the next bit. This continues until both start and goal become zero.

Complexity

  • Time complexity: The time complexity is \(O(\log(\max(\text{start}, \text{goal})))\) because we are iterating over the bits of the larger number, and the number of bits to process is proportional to the number of bits required to represent the larger number.

  • Space complexity: The space complexity is \(O(1)\) because we are using only a constant amount of extra space, regardless of the input size.

Code

class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        res = 0
        while start or goal:
            a = start & 1
            b = goal & 1
            if a != b:
                res += 1
            goal >>= 1
            start >>= 1
        return res

Editorial

Approach 1: Brute Force

class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        count = 0
        while start > 0 or goal > 0:
            # Increment count if the current bits differ
            if (start & 1) != (goal & 1):
                count += 1
            # Shift both numbers to the right to check the next bits
            start >>= 1
            goal >>= 1
        return count

Approach 2: Recursive Approach

class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        # Base case: both numbers have been fully processed
        if start == 0 and goal == 0:
            return 0

        # Flip for the current least significant bit
        flip = 1 if (start & 1) != (goal & 1) else 0

        # Recurse for the next bits by right-shifting both numbers
        return flip + self.minBitFlips(start >> 1, goal >> 1)

Approach 3: XOR Rules

class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        # XOR to find differing bits
        xor_result = start ^ goal
        count = 0
        # Count the number of 1s in xor_result (differing bits)
        while xor_result:
            count += xor_result & 1  # Increment if the last bit is 1
            xor_result >>= 1  # Shift right to process the next bit
        return count
  • time: O(number of bits)
  • space: O(1)

You may also enjoy