2220. Minimum Bit Flips to Convert Number

Problem Description

Given two integers start and goal, the task is to find the minimum number of bit flips required to convert start to goal. A bit flip involves changing a bit from 0 to 1 or 1 to 0.

Solution Approach

The most efficient way to solve this problem is using bit manipulation. The core idea is to use the XOR operator (^). The XOR operation compares corresponding bits of two numbers. If the bits are different, the result is 1; otherwise, it's 0. Therefore, start ^ goal will produce a number where each bit set to 1 represents a bit that needs to be flipped to transform start into goal. The number of bits set to 1 in this result is the minimum number of flips needed.

We can count the number of set bits (1s) using built-in functions provided by most programming languages (like bitCount in Java or .bit_count() in Python). Alternatively, we can manually iterate through the bits and count the 1s.

Time and Space Complexity Analysis

Time Complexity: O(log n), where n is the magnitude of the input integers. This is because the number of bits in the binary representation of an integer is proportional to the logarithm of its value (base 2). The built-in bitCount functions typically have a logarithmic time complexity or even better (constant time in some implementations). The manual bit counting method also takes logarithmic time.

Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size.

Code Implementation in Different Languages

Python

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

Java

class Solution {
    public int minBitFlips(int start, int goal) {
        return Integer.bitCount(start ^ goal);
    }
}

C++

class Solution {
public:
    int minBitFlips(int start, int goal) {
        return __builtin_popcount(start ^ goal);
    }
};

Go

func minBitFlips(start int, goal int) int {
	return bits.OnesCount(uint(start ^ goal))
}

JavaScript

var minBitFlips = function(start, goal) {
    let xorResult = start ^ goal;
    let count = 0;
    while (xorResult > 0) {
        count += xorResult & 1;
        xorResult >>= 1;
    }
    return count;
};

TypeScript

function minBitFlips(start: number, goal: number): number {
    let xorResult = start ^ goal;
    let count = 0;
    while (xorResult > 0) {
        count += xorResult & 1;
        xorResult >>= 1;
    }
    return count;
}

C

int minBitFlips(int start, int goal){
    int x = start ^ goal;
    int count = 0;
    while(x > 0){
        count += x & 1;
        x >>= 1;
    }
    return count;
}

These implementations all follow the same core logic: XOR the input numbers, then count the set bits in the result. The built-in functions make the code very concise and efficient. The manual bit-counting approach is also provided for educational purposes, showing the underlying mechanism. Choose the implementation that best suits your preferred language and coding style.