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.
This method avoids the overhead of string conversion by directly working with the bits of the number. After calculating the XOR of start and goal, it iteratively checks each bit of the result. A loop runs until the number becomes zero, and in each step, it checks the least significant bit (LSB) and then right-shifts the number to process the next bit.
Algorithm
- Calculate
n = start ^ goal. - Initialize
flips = 0. - Loop while
n > 0:- Check the least significant bit (LSB) of
nusing(n & 1). - If the LSB is 1, increment
flips. - Right-shift
nby one position to process the next bit (n = n >> 1).
- Check the least significant bit (LSB) of
- Return
flips.
Walkthrough
This approach improves upon the string conversion method by eliminating the need for an intermediate string, thus saving space and time. It works by repeatedly checking the last bit of the number and then shifting the bits to the right.
- Calculate the XOR result:
int n = start ^ goal;. - Initialize a counter
flips = 0. - Use a
whileloop that continues as long asnis greater than 0. - Inside the loop, use the bitwise AND operator (
&) to check if the last bit is a 1:(n & 1) == 1. If it is, we increment ourflipscounter. - Right-shift
nby one bit (n = n >> 1;) to discard the last bit and expose the next one. - The loop terminates when all bits have been shifted out and
nbecomes 0.
class Solution { public int minBitFlips(int start, int goal) { int n = start ^ goal; int flips = 0; while (n > 0) { // Add the last bit to the count flips += (n & 1); // Right shift to check the next bit n = n >> 1; } return flips; }}Complexity
Time
O(k), where `k` is the number of bits in an integer (e.g., 32). The loop runs `k` times in the worst case for a `k`-bit integer.
Space
O(1), as it only uses a few variables for calculation, regardless of the input size.
Trade-offs
Pros
More efficient than the string conversion method as it avoids creating intermediate data structures.
Operates directly on bits, which is generally faster.
Constant space complexity.
Cons
The number of iterations is proportional to the total number of bits in the integer type (e.g., 32), not the actual number of set bits. It will always loop about 32 times for a large number, even if only one bit needs to be flipped.
This is a clever optimization over the simple iterative approach, known as Brian Kernighan's algorithm. Instead of checking every single bit, this algorithm repeatedly finds and removes the rightmost set bit. The number of times this operation can be performed is exactly equal to the number of set bits. This significantly reduces the number of loop iterations if the number of set bits is small.
Algorithm
- Calculate
n = start ^ goal. - Initialize
flips = 0. - Loop while
n > 0:- Apply the operation
n = n & (n - 1). This unsets the rightmost '1' bit. - Increment
flips.
- Apply the operation
- Return
flips.
Walkthrough
Brian Kernighan's algorithm provides an efficient way to count set bits. The key insight is that for any number n, the operation n & (n - 1) unsets the rightmost set bit of n. By repeatedly applying this operation and counting how many times we can do it before the number becomes 0, we can find the total number of set bits.
- Calculate the XOR result:
int n = start ^ goal;. - Initialize a counter
flips = 0. - Use a
whileloop that continues as long asnis not zero. - Inside the loop, we increment
flipsand then updatenwithn & (n - 1). - The loop will execute exactly as many times as there are set bits in the initial
n.
class Solution { public int minBitFlips(int start, int goal) { int n = start ^ goal; int flips = 0; while (n > 0) { // This operation removes the rightmost set bit n = n & (n - 1); flips++; } return flips; }}Complexity
Time
O(m), where `m` is the number of set bits (i.e., differing bits). In the worst case, this is `O(k)` where `k` is the total number of bits, but it's much faster on average.
Space
O(1), as no extra space proportional to the input size is used.
Trade-offs
Pros
Highly efficient. The number of loop iterations is equal to the number of set bits, not the total number of bits.
Constant space complexity.
Significantly faster than the previous approaches when the number of differing bits is small.
Cons
The logic
n & (n - 1)might be less intuitive for beginners compared to a simple bit check and shift.
The most efficient and simplest approach is to use the language's built-in function for counting set bits (also known as population count or Hamming weight). These functions are typically implemented using highly optimized machine code instructions, making them extremely fast.
Algorithm
- Calculate
n = start ^ goal. - Return the result of a built-in function to count set bits in
n(e.g.,Integer.bitCount(n)in Java).
Walkthrough
Modern programming languages and hardware provide optimized ways to perform common bitwise operations. Counting the number of set bits is one such operation. In Java, the Integer wrapper class provides the bitCount() static method for this purpose.
The solution becomes a one-liner:
- Calculate the bitwise XOR of
startandgoalto get a number representing the differing bits. - Pass this result to
Integer.bitCount(). - Return the value.
This approach is not only the most performant but also the most readable and least error-prone.
class Solution { public int minBitFlips(int start, int goal) { // 1. XOR finds the bits that are different. // 2. bitCount counts the number of set bits (1s). return Integer.bitCount(start ^ goal); }}Complexity
Time
O(1). The `Integer.bitCount` method is often mapped to a hardware instruction which takes a constant number of cycles.
Space
O(1).
Trade-offs
Pros
The most efficient method, often implemented using a single CPU instruction (like POPCNT).
Extremely concise and readable code.
Guaranteed to be correct and highly optimized by the platform.
Cons
Abstracts away the underlying bit manipulation logic, which might not be ideal for learning purposes or in environments where such functions are not available.
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; }}/** * @param {number} start * @param {number} goal * @return {number} */ var minBitFlips = function (start, goal) { return bitCount(start ^ goal); };function bitCount(i) { i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); return i & 0x3f;}class Solution {public: int minBitFlips(int start, int goal) { int t = start ^ goal; int ans = 0; while (t) { ans += t & 1; t >>= 1; } return ans; }};class Solution: def minBitFlips(self, start: int, goal: int) -> int: t = start ^ goal ans = 0 while t: ans += t & 1 t >>= 1 return ansVideo 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.