Minimum Bit Flips to Convert Number

Easy

Amazon

2 views

Topics:

Bit Manipulation

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.

For example:

If start = 10 and goal = 7, the output should be 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.
If start = 3 and goal = 4, the output should be 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.

Write a function to solve this problem efficiently.

Minimum Bit Flips to Convert Number

Easy

Amazon

2 views

Topics:

Bit Manipulation

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.

For example:

If start = 10 and goal = 7, the output should be 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.
If start = 3 and goal = 4, the output should be 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.

Write a function to solve this problem efficiently.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are `start` and `goal` guaranteed to be non-negative integers?
What is the maximum possible value for `start` and `goal`? This will help me determine the optimal bit manipulation strategy.
If `start` and `goal` are equal, should I return 0?
Can I assume that `start` and `goal` are always valid integers and I don't need to handle null or invalid input?
Are we aiming for the most efficient solution, assuming inputs can become arbitrarily large?

Brute Force Solution

Approach

The goal is to figure out how many changes we need to make to one number to turn it into another. The brute force method directly compares each matching part of the numbers and counts the differences.

Here's how the algorithm would work step-by-step:

Look at the two numbers we want to compare.
Consider each part of the numbers in order from right to left.
If the parts are different, count that as one change.
If the parts are the same, don't add anything to the count.
Keep going through all the parts of the numbers.
The total count of differences is the answer.

Code Implementation

def min_bit_flips_brute_force(start_number, goal_number):
    bit_flip_count = 0
    
    # Convert integers to binary strings
    start_number_binary = bin(start_number)[2:]
    goal_number_binary = bin(goal_number)[2:]

    # Find the length of the longer binary string
    max_length = max(len(start_number_binary), len(goal_number_binary))

    # Pad the shorter string with leading zeros to match lengths. Important for comparison.
    start_number_binary = start_number_binary.zfill(max_length)
    goal_number_binary = goal_number_binary.zfill(max_length)

    for bit_index in range(max_length):
        # Compare bits at each index and increment the flip count if they differ.
        if start_number_binary[bit_index] != goal_number_binary[bit_index]:
            bit_flip_count += 1

    return bit_flip_count

Big(O) Analysis

Time Complexity

O(1) – The described brute force method iterates through the bits of the two input numbers, comparing them one by one. The number of bits to compare is determined by the size of the input integers, which is typically fixed (e.g., 32 bits or 64 bits). Therefore, the number of operations is constant regardless of the specific values of the input integers. This constant number of operations results in a time complexity of O(1).

Space Complexity

O(1) – The provided plain English explanation describes a process that directly compares parts of the input numbers and counts the differences. It doesn't mention creating or using any auxiliary data structures like lists, arrays, hash maps, or recursion. The algorithm seems to operate in place, only needing a counter variable to keep track of the number of differing bits. Therefore, the space required is constant, independent of the size of the input numbers.

Optimal Solution

Approach

The goal is to find the minimum number of bit flips needed to transform one number into another. Instead of comparing all bits individually, a key insight is to isolate the bits that are different between the two numbers using an exclusive OR operation.

Here's how the algorithm would work step-by-step:

Perform an exclusive OR (XOR) operation on the two numbers. This will give you a new number where each bit is 1 if the corresponding bits in the original numbers were different, and 0 if they were the same.
Count the number of '1' bits in the result of the XOR operation. Each '1' bit represents a position where the bits were different, and therefore needs to be flipped to convert one number into the other.
The total count of '1' bits will directly give you the minimum number of flips required.

Code Implementation

def min_bit_flips(start_number, goal_number):
    # XOR identifies differing bits.
    xor_result = start_number ^ goal_number

    bit_flips_needed = 0

    # Count the number of set bits.
    while xor_result > 0:
        # Check the rightmost bit.
        if (xor_result & 1) == 1:
            bit_flips_needed += 1

        # Right-shift to check the next bit.
        xor_result >>= 1

    return bit_flips_needed

Big(O) Analysis

Time Complexity

O(1) – The XOR operation is a single bitwise operation and takes constant time. Counting the set bits in the result involves iterating through the bits of an integer. Since the size of an integer is fixed (e.g., 32 or 64 bits), the number of iterations is constant and independent of any input variable. Therefore, the time complexity is O(1).

Space Complexity

O(1) – The algorithm performs a bitwise XOR operation and then counts the number of 1s in the result. It does not create any auxiliary data structures like arrays, lists, or hash maps. It only uses a few integer variables to store the XOR result and the count of 1s. Therefore, the space used is constant and independent of the input numbers, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Both start and goal are zero	Return 0, as no bits need to be flipped.
Start and goal are the same number	Return 0, as no bits need to be flipped.
Start is zero, goal is a large positive number	The number of flips will equal the number of set bits in the goal, and the solution should efficiently count them.
Start is a large positive number, goal is zero	The number of flips will equal the number of set bits in the start, and the solution should efficiently count them.
Integer overflow if intermediate calculations are not handled carefully	Bitwise XOR operation is used, which inherently avoids overflow concerns.
Maximum integer value for start or goal	The bitwise XOR and bit counting will work correctly with maximum integer values.
Negative integer inputs (if applicable depending on language and problem constraints)	If negative numbers are allowed, use unsigned right shift (>>> in Java, etc.) to ensure logical shifts, and handle the sign bit correctly or ensure input is within acceptable range (non-negative).
Inputs where start and goal only differ by one or two bits.	The bit counting algorithm should correctly handle small differences between the numbers.