#2220
Minimum Bit Flips to Convert Number
newbie · 100 · lc easy +12 · verified · 87.8% accepted · 1,596 likes · top 98%
Description
Flipping a bit in a number x means selecting any bit in its binary representation and switching it from 0 to 1 or from 1 to 0.
- For instance, for x = 7, the binary form is 111 and any bit position (including leading zero positions) may be flipped. Flipping the rightmost bit gives 110, flipping the second-from-right gives 101, flipping the fifth bit gives 10111, etc.
Given two integers start and goal, return the fewest bit flips required to transform start into 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.
Code
1
2
3