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.
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 <= 109Note: This question is the same as 461: Hamming Distance.
The goal of #2220 Minimum Bit Flips to Convert Number is to determine how many bit positions must change to transform one integer into another. Since numbers are stored in binary, a flip is required whenever the corresponding bits of the two numbers differ.
A clean way to identify differing bits is by using the XOR operation. When we compute start ^ goal, the resulting number has 1 in every position where the bits are different and 0 where they are the same. Therefore, the task reduces to counting how many 1 bits exist in this XOR result.
You can count these bits using built‑in bit counting functions or by repeatedly checking the least significant bit and shifting the number. This approach leverages efficient bit manipulation and avoids converting numbers to strings or arrays.
The algorithm runs in constant time relative to integer size and requires minimal extra space, making it an optimal solution for this easy interview-style problem.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| XOR + Count Set Bits | O(1) | O(1) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
If the value of a bit in start and goal differ, then we need to flip that bit.
Consider using the XOR operation to determine which bits need a bit flip.
The simplest way to determine the different bits between two numbers is to use the XOR operation. XORing two bits will yield 1 if the bits are different and 0 if they are the same. Thus, XORing two numbers will produce a number with bits set at positions where the input numbers have different bits. Counting the number of 1s in this result will give the number of flips required.
Time Complexity: O(n) where n is the number of bits in the maximum of the two numbers, as you may have to check each bit once.
Space Complexity: O(1) as no additional space is used.
1public class MinFlips {
2 public static int minFlips(int start, int goal) {
3 int xor = start ^ goal;
4
The Java implementation follows a similar approach by using XOR to identify mismatched bits and counting those differing bits iteratively.
Many languages offer built-in functions to count the number of set bits (ones) in a binary number. Utilizing these handy functions can make our solution more concise and often more efficient. The bitwise XOR is computed between the two numbers, and the solution boils down to counting the number of set bits in the result.
Time Complexity: O(1) on systems where built-ins are optimized.
Space Complexity: O(1) since we use no additional resources.
class MinFlips {
public static int MinFlipsCalc(int start, int goal) {
return CountBitsPopCount(start ^ goal);
}
static int CountBitsPopCount(int num) {
return Convert.ToString(num, 2).Count(c => c == '1');
}
static void Main(string[] args) {
int start = 10, goal = 7;
Console.WriteLine(MinFlipsCalc(start, goal)); // Output: 3
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Easy bit manipulation problems like this are commonly used in coding interviews to test understanding of binary operations. While the exact question may vary, the XOR and set-bit counting pattern frequently appears in FAANG-style interview rounds.
XOR returns 1 when two bits are different and 0 when they are the same. This property makes it ideal for identifying exactly which bit positions need to change between the start and goal numbers.
No special data structure is required for this problem. The solution relies purely on bitwise operations on integers, particularly XOR and bit counting techniques.
The optimal approach uses bit manipulation with the XOR operator. By computing start ^ goal, you highlight all bit positions that differ. Counting the number of set bits in this result directly gives the number of flips required.
In C#, we can convert the XOR-ed result to a string in binary format, then use LINQ to count '1's, providing an efficient solution.