Minimum Bit Flips to Convert Number

Difficulty: Easy | Acceptance: 87.90% | Paid: No Topics: Bit Manipulation

A bit flip of a number x is choosing a bit position i (0-indexed) and flipping the value of that bit from 0 to 1 or from 1 to 0.

Given two integers start and goal, return the minimum number of bit flips to convert start to goal.

• Examples
• Constraints
• XOR and Brian Kernighan’s Algorithm
• XOR and Built-in Bit Count
• Bit by Bit Comparison
• String Conversion

Examples

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 by flipping the 1st, 2nd, and 4th bits from the right.

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 by flipping all three bits.

Constraints

0 <= start, goal <= 10^9

XOR and Brian Kernighan’s Algorithm

Intuition XOR of two numbers produces a result where each bit is 1 only where the original bits differ. Counting these 1s gives us the minimum flips needed. Brian Kernighan’s algorithm efficiently counts set bits by repeatedly clearing the rightmost set bit.

Steps

• Compute XOR of start and goal to find differing bit positions
• While XOR is not zero, clear the rightmost set bit using n & (n-1)
• Increment count for each cleared bit

class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        xor = start ^ goal
        count = 0
        while xor:
            xor &= xor - 1
            count += 1
        return count

Complexity

• Time: O(k) where k is the number of set bits in XOR result
• Space: O(1)
• Notes: Most efficient for sparse bit differences

XOR and Built-in Bit Count

Intuition After XOR to find differing bits, use language’s built-in population count function to directly count set bits in a single operation.

Steps

• Compute XOR of start and goal
• Use built-in bit count function to count 1s in the result

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

Complexity

• Time: O(1) - hardware instruction or constant time string conversion
• Space: O(1)
• Notes: Cleanest and most readable solution

Bit by Bit Comparison

Intuition Directly compare each bit position of both numbers using bitwise AND and right shift operations, counting positions where bits differ.

Steps

• Initialize count to 0
• While either number has remaining bits, compare the least significant bits
• If bits differ, increment count
• Right shift both numbers to process next bit

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

Complexity

• Time: O(log n) where n is the larger of start and goal
• Space: O(1)
• Notes: Intuitive but less efficient than XOR-based approaches

String Conversion

Intuition Convert both numbers to binary strings, pad them to equal length, then compare characters to count differing positions.

Steps

• Convert both numbers to binary strings
• Pad shorter string with leading zeros
• Compare each character position
• Count positions where characters differ

class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        max_len = max(start.bit_length(), goal.bit_length())
        start_bin = format(start, f'0{max_len}b')
        goal_bin = format(goal, f'0{max_len}b')
        
        count = 0
        for s, g in zip(start_bin, goal_bin):
            if s != g:
                count += 1
        return count

Complexity

• Time: O(log n) for string conversion and comparison
• Space: O(log n) for storing binary strings
• Notes: Less efficient due to string allocation overhead