2220. Minimum Bit Flips to Convert Number LeetCode Solution
In this guide, you will get 2220. Minimum Bit Flips to Convert Number LeetCode Solution with the best time and space complexity. The solution to Minimum Bit Flips to Convert Number problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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
Note: This question is the same as 461: Hamming Distance.
Complexity Analysis
Time Complexity: O(\log (\max(\texttt{start}, \texttt{goal})))
Space Complexity: O(1)
2220. Minimum Bit Flips to Convert Number LeetCode Solution in C++
class Solution {
public:
int minBitFlips(unsigned start, unsigned goal) {
return popcount(start ^ goal);
}
}; /* code provided by PROGIEZ */
2220. Minimum Bit Flips to Convert Number LeetCode Solution in Java
class Solution {
public int minBitFlips(int start, int goal) {
return Integer.bitCount(start ^ goal);
}
} // code provided by PROGIEZ
2220. Minimum Bit Flips to Convert Number LeetCode Solution in Python
class Solution:
def minBitFlips(self, start: int, goal: int) -> int:
return (start ^ goal).bit_count() # code by PROGIEZ
