Minimum Bit Flips to Convert Number | Leetcode 2220 | Optimal Solution in Python

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.

Here’s the [Problem Link] to begin with.

Example 1:

Input: start = 10, goal = 7
Output: 3
Explanation: The binary representation of 10 and 7 are 1010 and 0111 respectively. We can convert 10 to 7 in 3 steps:
- Flip the first bit from the right: 1010 -> 1011.
- Flip the third bit from the right: 1011 -> 1111.
- Flip the fourth bit from the right: 1111 -> 0111.
It can be shown we cannot convert 10 to 7 in less than 3 steps. Hence, we return 3.

Example 2:

Input: start = 3, goal = 4
Output: 3
Explanation: The binary representation of 3 and 4 are 011 and 100 respectively. We can convert 3 to 4 in 3 steps:
- Flip the first bit from the right: 011 -> 010.
- Flip the second bit from the right: 010 -> 000.
- Flip the third bit from the right: 000 -> 100.
It can be shown we cannot convert 3 to 4 in less than 3 steps. Hence, we return 3.

Constraints:

• 0 <= start, goal <= 109

Solution 1: Optimal Approach (Bitwise Shift)

Intuition

Imagine you have two binary numbers, like two strings of lights where some are on (1) and some are off (0). To make the first string match the second, you need to flip the switches that are different. The quickest way to spot the differences is using XOR – it highlights exactly where the bits don’t match (gives 1 where different). Then, we just count how many 1s are in that XOR result – that’s the number of flips needed!

Detailed Approach

1. Compute XOR: Do start ^ goal to get a number where each 1 bit represents a position that needs flipping.
2. Count Set Bits: Loop through each possible bit position (0 to 31 for 32-bit integers) and check if that bit is set (1) in the XOR result.
3. Increment Count: Every time a bit is set, add 1 to our count – that’s one flip needed.
4. Return the Count: This gives the minimum flips since each differing bit must be flipped exactly once.

Code

class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        ans = start ^ goal  # XOR to find differing bits
        count = 0           # Counter for number of flips
        
        # Check each of the 32 bits
        for i in range(0, 32):
            # If the i-th bit is set (1), increment count
            if ans & (1 << i) != 0:
                count += 1
        
        return count

Code Explanation

We first XOR the two numbers, which creates a new number where every bit that’s different between start and goal is set to 1. Then, we loop through all 32 possible bits (since integers are 32-bit). For each bit position i, we use a bitwise AND with (1 shifted left by i) to check if that bit is 1. If it is, we know that’s a difference, so we add 1 to our flip count. This way, we’re basically counting how many bits need to be flipped without converting to binary strings.

Dry Run

Let’s take start = 10 (binary: 1010), goal = 7 (binary: 0111)

Step 1: XOR

• 1010 ^ 0111 = 1101 (13 in decimal)

Step 2: Count Set Bits

• i=0: 1101 & 0001 = 0001 ≠ 0 → count=1
• i=1: 1101 & 0010 = 0000 = 0 → count=1
• i=2: 1101 & 0100 = 0100 ≠ 0 → count=2
• i=3: 1101 & 1000 = 1000 ≠ 0 → count=3
• Higher bits are 0, so stop

Result: 3 flips needed

Time and Space Complexity

• Time Complexity: O(1) – We always loop 32 times, regardless of input size (fixed for 32-bit integers)
• Space Complexity: O(1) – We only use a few integer variables

Simplifying It

This is like comparing two binary fingerprints and counting the smudges (differences). XOR does the comparison in one go, and the loop just tallies up the mismatches. Super fast and no extra space needed!

Solution 2: Optimal Approach (While Loop)

Intuition

Again, we use XOR to find the differing bits, just like in the first approach. But instead of checking each bit position one by one, we can keep dividing the XOR result by 2 (right shift) and check if the last bit is 1 each time. It’s like peeling off the bits one by one from the end and counting how many are standing up (set to 1).

Detailed Approach

1. Compute XOR: Same as before – start ^ goal gives us the differing bits.
2. While Loop: While the XOR result is greater than 0, check if it’s odd (last bit is 1), add to count if yes.
3. Divide by 2: Divide the number by 2 to shift right and check the next bit.
4. Repeat: Continue until all bits are processed (number becomes 0).
5. Return the Count: This is our minimum flips.

Code

class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        ans = start ^ goal  # XOR to find differing bits
        count = 0           # Counter for number of flips
        
        # While there are bits left to check
        while ans > 0:
            # If last bit is 1 (odd number), increment count
            if ans % 2 == 1:
                count += 1
            # Divide by 2 to shift right
            ans = ans // 2
        
        return count

Code Explanation

After XOR, we get a number with 1s where bits differ. In the while loop, we check if the number is odd (ans % 2 == 1), which means the least significant bit is 1 – that’s a flip needed! Then we divide by 2 (integer division) to remove that bit and shift everything right. We repeat this until the number is 0. This effectively counts all the 1 bits in the binary representation.

Dry Run

Let’s take start = 10 (binary: 1010), goal = 7 (binary: 0111)

Step 1: XOR

• 1010 ^ 0111 = 1101 (13 in decimal)

Step 2: While Loop

• ans=13 (1101), 13%2=1 → count=1, ans=6 (0110)
• ans=6 (0110), 6%2=0 → count=1, ans=3 (0011)
• ans=3 (0011), 3%2=1 → count=2, ans=1 (0001)
• ans=1 (0001), 1%2=1 → count=3, ans=0 (0000)
• Loop ends

Result: 3 flips needed

Time and Space Complexity

• Time Complexity: O(log n) – We loop as many times as there are bits in the number (up to 32 for integers)
• Space Complexity: O(1) – Just a few variables, no extra space

Simplifying It

This is like slicing off the end of a binary number repeatedly and checking if it’s a 1 each time. If it is, that’s a flip! It’s even simpler than the first method because there’s no fixed loop – it stops when there are no more bits to check.

Summary

Both solutions are super efficient and use the power of XOR to find differences quickly. The first one is great if you like explicit bit checking, while the second is more concise and adapts to the number’s size. In interviews, either works, but mention XOR as the key trick!

If you’re practicing for LeetCode or interviews, try implementing these yourself and experiment with different numbers. Got questions? Drop them in the comments – happy coding! 🚀

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.