Minimum Bit Flips to Convert Number

Leetcode Problem:

• Minimum Bit Flips to Convert Number

Summary

• Find the minimum number of bit flips to convert start to goal.

Approach

• This solution works by continuously dividing both start and goal by 2 (using bitwise right shift) until they are both 0
• In each iteration, it checks if the least significant bit of start and goal are different
• If they are, it increments the answer by 1
• This is because flipping the least significant bit of either start or goal (or both) requires one bit flip.

Complexity

• O(log min(start, goal))

Explain

• The time complexity of this solution is O(log min(start, goal)) because in each iteration, the size of start and goal is halved
• The space complexity is O(1) because only a constant amount of space is used.

Solution Code:

class Solution {
public:
    int minBitFlips(int start, int goal) {
        int ans = 0;
        while(!(start == 0 && goal == 0)){
            if((start & 1) != (goal & 1)) ans++;
            start >>= 1;
            goal >>= 1;
        }
        return ans;
    }
};