#2220

Easy

auto_awesomeBit Manipulation-driven solution strategy

LeetCode Problem Workspace

Minimum Bit Flips to Convert Number

Determine the minimum number of bit flips required to convert one integer to another using precise bit manipulation.

Problem Statement

Given two non-negative integers, start and goal, you need to calculate the minimum number of bit flips required to convert start into goal. A bit flip changes a 0 to 1 or a 1 to 0 at a specific position in the binary representation.

Return the minimum count of bit flips necessary to achieve the transformation. For example, converting start = 10 to goal = 7 requires examining the binary forms 1010 and 0111 and counting positions where bits differ.

Examples

Example 1

Input: start = 10, goal = 7

Output: 3

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

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 Approach

Use XOR to Identify Differing Bits

Compute start XOR goal. Each 1 in the XOR result indicates a bit that differs and must be flipped. This directly targets the bits that require change without affecting unchanged positions.

Count the Set Bits Efficiently

Once XOR is computed, count the number of set bits in the result. Each set bit corresponds to one required flip. This can be done using Brian Kernighan's algorithm for efficiency, reducing unnecessary iterations.

Return the Minimum Flip Count

The total number of set bits in the XOR result is the minimum number of flips needed. This guarantees optimality because each differing bit must be flipped exactly once to match goal.

Complexity Analysis

Metric	Value
Time	O(\text{number of set bits})
Space	O(1)

Time complexity is O(number of set bits) because we only iterate over differing bits using efficient bit counting. Space complexity is O(1) as no extra storage proportional to input size is needed.

What Interviewers Usually Probe

Look for direct bit manipulation solutions using XOR rather than iterative bit flipping.
Check if candidate counts differing bits accurately without redundant operations.
Watch if they handle edge cases where start or goal is zero efficiently.

Common Pitfalls or Variants

Common pitfalls

Attempting to simulate each flip step instead of using XOR leads to unnecessary complexity.
Failing to count only differing bits can result in off-by-one errors.
Ignoring integer constraints might cause overflow in some languages.

Follow-up variants

Compute minimum bit flips for arrays of numbers pairwise.
Determine bit flips required to convert start to goal under a fixed number of bits.
Count flips to match multiple goals simultaneously using bitwise aggregation.

FAQ

What is the easiest way to count the minimum bit flips between two numbers?

Use XOR between start and goal and then count the set bits in the result, each representing one necessary flip.

Does this problem require iterating through all bit positions manually?

No, XOR combined with efficient bit counting eliminates the need to check each bit individually.

What pattern does this problem exemplify in GhostInterview terms?

This problem exemplifies a Bit Manipulation-driven solution strategy focused on detecting differing bits directly.

Are there constraints on the input numbers?

Yes, both start and goal are non-negative integers between 0 and 10^9 inclusive.

Can the minimum flips ever be zero?

Yes, if start and goal are identical, no bit flips are required, so the minimum is zero.

terminal

Solution

Solution 1: Bit Manipulation

According to the problem description, we only need to count the number of 1s in the binary representation of $\textit{start} \oplus \textit{goal}$.

1

2

3

class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        return (start ^ goal).bit_count()

Continue Practicing

#2212 maximum points in an archery competition #2206 divide array into equal pairs #2172 maximum and sum of array