2220. Minimum Bit Flips to Convert Number

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.

Example 1:

Input: start = 10, goal = 7
Output: 3
Explanation: 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
Explanation: 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

Approach 01:

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

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

Time Complexity

• Computing XOR:

  The operation start ^ goal computes the bitwise XOR between start and goal. This operation runs in \(O(1)\) time, as it directly operates on fixed-size integers.

• Counting Set Bits (Population Count):

  The function __popcount counts the number of set bits (1s) in the result of the XOR operation. The time complexity of counting set bits in an integer is \(O(1)\) because the integer size is constant (e.g., 32 or 64 bits), making the operation independent of input size.

• Overall Time Complexity:

  The overall time complexity is \(O(1)\), as both the XOR computation and the population count run in constant time.

Space Complexity

• Space for Variables:

  The solution uses a constant amount of space for the input integers start and goal, and the result of the XOR operation. The space complexity for these operations is \(O(1)\).

• Overall Space Complexity:

  The overall space complexity is \(O(1)\), as no additional data structures or dynamic memory allocations are used.