LeetCode 2220 - Minimum Bit Flips to Convert Number

The problem asks us to determine the minimum number of bit flips required to transform an integer start into another integer goal. A bit flip is defined as changing a single bit in the binary representation of a number from 0 to 1 or from 1 to 0.

leetcodeeasybit-manipulation

LeetCode Problem 2220

Difficulty: 🟢 Easy
Topics: Bit Manipulation

Solution

Problem Understanding

The problem asks us to determine the minimum number of bit flips required to transform an integer start into another integer goal. A bit flip is defined as changing a single bit in the binary representation of a number from 0 to 1 or from 1 to 0. The input consists of two non-negative integers start and goal, both of which can range up to $10^9$. The expected output is a single integer representing the minimum number of flips needed.

Essentially, the problem is asking for the number of positions in the binary representations of start and goal where the bits differ. This is equivalent to calculating the Hamming distance between the two numbers.

Key considerations include handling numbers with different bit lengths, numbers that are equal (resulting in zero flips), and very large numbers up to 30 bits (since $10^9 < 2^{30}$). Edge cases might include start or goal being zero or one being significantly larger than the other.

Approaches

The brute-force approach involves converting both start and goal into their binary string representations, aligning their lengths, and then iterating through each bit to count differences. While this works, it involves string manipulation and bit-by-bit comparison, which is unnecessary because bitwise operators are available. This approach has linear time complexity relative to the number of bits, but it is not optimal due to the overhead of string operations.

The optimal approach leverages the bitwise XOR operation. XOR between two bits is 1 if the bits differ and 0 if they are the same. Thus, start ^ goal produces a number where each 1 represents a bit that needs to be flipped. Counting the number of 1s in this XOR result gives the minimum number of flips. This is efficient because it directly works at the bit level without any conversion to strings.

Approach Time Complexity Space Complexity Notes
Brute Force O(B) O(B) Convert numbers to binary strings and compare each bit
Optimal O(B) O(1) Use XOR to identify differing bits and count set bits

Here, $B$ represents the number of bits needed to represent the numbers, which is at most 30 for the given constraints.

Algorithm Walkthrough

  1. Compute the XOR of start and goal. This gives a number where each 1 represents a bit that differs between the two numbers.
  2. Initialize a counter flips to zero to track the number of differing bits.
  3. While the XOR result is greater than zero, repeatedly remove the least significant 1 using xor &= xor - 1. Increment flips each time. This technique counts the number of set bits efficiently.
  4. Once all 1s have been removed, the counter flips contains the minimum number of bit flips required.
  5. Return flips as the result.

Why it works: XOR produces a binary number where each 1 indicates a position that differs between start and goal. Counting all such 1s gives the exact number of bits that need to be flipped. The property x & (x - 1) clears the lowest set bit efficiently, ensuring all differing bits are counted.

Python Solution

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

The Python implementation computes the XOR of start and goal to identify differing bits. It then counts the number of set bits using a loop with the efficient xor &= xor - 1 trick. Each iteration removes one set bit and increments the flips counter until no set bits remain.

Go Solution

func minBitFlips(start int, goal int) int {
    xor := start ^ goal
    flips := 0
    for xor != 0 {
        xor &= xor - 1
        flips++
    }
    return flips
}

In Go, the implementation is essentially the same as in Python. Go uses int for integers, and bitwise operations work directly on integers. The loop counts set bits in the XOR result using the same efficient bit-clearing method.

Worked Examples

Example 1: start = 10, goal = 7

Binary representations: 10 = 1010, 7 = 0111

  1. XOR: 1010 ^ 0111 = 1101
  2. Count set bits in 1101: 3

Result: 3 flips.

Example 2: start = 3, goal = 4

Binary representations: 3 = 011, 4 = 100

  1. XOR: 011 ^ 100 = 111
  2. Count set bits in 111: 3

Result: 3 flips.

Step XOR Value Flips Count
Initial 1010 ^ 0111 = 1101 0
Remove lowest 1 1100 1
Remove lowest 1 1000 2
Remove lowest 1 0000 3

Complexity Analysis

Measure Complexity Explanation
Time O(B) B is the number of bits in the XOR result, maximum 30
Space O(1) Only a few integer variables are used

The algorithm is efficient because it processes only the set bits in the XOR result. Given the constraint $0 \leq start, goal \leq 10^9$, the number of bits never exceeds 30, making the approach effectively constant time in practice.

Test Cases

# Basic test cases from the problem
assert Solution().minBitFlips(10, 7) == 3  # 1010 -> 0111
assert Solution().minBitFlips(3, 4) == 3   # 011 -> 100

# Edge cases
assert Solution().minBitFlips(0, 0) == 0   # no flips needed
assert Solution().minBitFlips(0, 1) == 1   # only one flip
assert Solution().minBitFlips(1, 0) == 1   # only one flip

# Large numbers
assert Solution().minBitFlips(10**9, 0) == 30  # 30-bit number
assert Solution().minBitFlips(10**9, 10**9) == 0  # same number, zero flips

# Different bit lengths
assert Solution().minBitFlips(1, 8) == 2  # 0001 -> 1000, 2 flips
Test Why
10,7 Provided example with multiple flips
3,4 Provided example with multiple flips
0,0 Minimal input, no flips
0,1 and 1,0 Single bit difference, minimal flips
10^9,0 Maximum input, test large numbers
10^9,10^9 Identical numbers, expect zero flips
1,8 Different bit lengths, verify correct bit counting

Edge Cases

  1. Start and goal are the same: This is a potential source of error if the implementation incorrectly counts flips even when numbers are equal. The correct output is zero flips because XOR of two identical numbers is zero.
  2. Numbers with leading zeros in binary representation: A naive string-based solution may ignore leading zeros, leading to incorrect counts. The bitwise XOR method inherently handles all bits, including leading zeros, ensuring correctness.
  3. Maximum possible values: With numbers up to $10^9$, the XOR result can have up to 30 bits. The solution must efficiently handle counting bits without converting to strings or using large arrays. The xor &= xor - 1 technique guarantees efficiency for large inputs.