Watch 10 video solutions for Minimum Bit Flips to Convert Number, a easy level problem involving Bit Manipulation. This walkthrough by take U forward has 166,149 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 109
Note: This question is the same as 461: Hamming Distance.
Problem Overview: You are given two integers, start and goal. The task is to determine the minimum number of bit flips required to convert start into goal. A bit flip means changing a 0 to 1 or a 1 to 0 in the binary representation.
Approach 1: XOR and Bit Counting (Time: O(1), Space: O(1))
The key observation: a bit needs to flip only when the corresponding bits in start and goal differ. Using start ^ goal highlights exactly those positions. In XOR, matching bits produce 0 while different bits produce 1. After computing the XOR result, count how many 1 bits appear in that number. Each 1 represents a required flip. This solution relies on basic bit manipulation operations and simple bit counting. Since integers are bounded by fixed bit width (typically 32 bits), the operation runs in constant time and constant space.
Approach 2: Built-in PopCount (Time: O(1), Space: O(1))
Many languages expose optimized CPU instructions for counting set bits through functions like __builtin_popcount in C++, Integer.bitCount() in Java, or bin(x).count('1') in Python. The workflow stays the same: compute diff = start ^ goal, then call a built-in population count function to count the number of 1 bits. These functions are heavily optimized and often map directly to hardware instructions. This makes the code shorter and often slightly faster in practice while still relying on the same bit manipulation principle. The algorithmic complexity remains constant because the bit width of integers is fixed.
Recommended for interviews: The XOR + bit counting approach is the expected solution. Interviewers want to see that you recognize XOR as a tool for detecting differing bits. Writing a small loop to count set bits demonstrates understanding, while using a built-in popcount shows familiarity with language features. Both solutions operate in O(1) time and O(1) space and rely on fundamental bit manipulation concepts.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| XOR + Manual Bit Count | O(1) | O(1) | When demonstrating understanding of XOR and bit operations in interviews |
| XOR + Built-in PopCount | O(1) | O(1) | When the language provides optimized bit counting utilities |