Minimum Bit Flips to Convert Number
EasyPrompt
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 is111and we may choose any bit (including any leading zeros not shown) and flip it. We can flip the first bit from the right to get110, flip the second bit from the right to get101, flip the fifth bit from the right (a leading zero) to get10111, 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.Approaches
4 approaches with complexity analysis and trade-offs.
This approach first calculates the bitwise XOR of start and goal. The result of this operation is a number where each set bit (1) represents a position where the original numbers' bits differ. The problem then becomes counting the set bits in this new number. This approach converts the number to its binary string representation and then iterates through the string to count the occurrences of the character '1'.
Algorithm
- Calculate
xorResult = start ^ goal. - Convert
xorResultto its binary string representation. - Initialize a counter
flips = 0. - Iterate through each character of the binary string.
- If a character is '1', increment the
flipscounter. - Return
flips.
Walkthrough
The fundamental insight is that the minimum number of bit flips to convert start to goal is equal to the number of positions at which their binary representations differ. The bitwise XOR operation (^) is perfect for this, as start ^ goal produces a number where a bit is set to 1 if and only if the corresponding bits in start and goal were different.
This approach proceeds as follows:
- Compute
int xorResult = start ^ goal;. - Convert
xorResultto a binary string:String binaryString = Integer.toBinaryString(xorResult);. - Iterate through this string and count the number of '1's. This count is the number of differing bits, which is our answer.
class Solution { public int minBitFlips(int start, int goal) { int xorResult = start ^ goal; String binaryString = Integer.toBinaryString(xorResult); int flips = 0; for (char c : binaryString.toCharArray()) { if (c == '1') { flips++; } } return flips; }}Complexity
Time
O(log N), where N is the value of `start ^ goal`. The time is dominated by converting the number to a string and iterating over it, and the length of the binary string is proportional to `log N`.
Space
O(log N), where N is the value of `start ^ goal`. This space is required to store the binary string representation.
Trade-offs
Pros
Conceptually simple and easy to understand for beginners.
Leverages built-in string conversion, making the initial implementation straightforward.
Cons
Inefficient in terms of both time and space due to the creation of an intermediate string.
String operations are generally slower than bitwise manipulations.
Solutions
Solution
class Solution {public int minBitFlips(int start, int goal) { int t = start ^ goal; int ans = 0; while (t != 0) { ans += t & 1; t >>= 1; } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.