Watch 10 video solutions for Number of Steps to Reduce a Number in Binary Representation to One, a medium level problem involving String, Bit Manipulation. This walkthrough by codestorywithMIK has 13,171 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the binary representation of an integer as a string s, return the number of steps to reduce it to 1 under the following rules:
If the current number is even, you have to divide it by 2.
If the current number is odd, you have to add 1 to it.
It is guaranteed that you can always reach one for all test cases.
Example 1:
Input: s = "1101" Output: 6 Explanation: "1101" corressponds to number 13 in their decimal representation. Step 1) 13 is odd, add 1 and obtain 14. Step 2) 14 is even, divide by 2 and obtain 7. Step 3) 7 is odd, add 1 and obtain 8. Step 4) 8 is even, divide by 2 and obtain 4. Step 5) 4 is even, divide by 2 and obtain 2. Step 6) 2 is even, divide by 2 and obtain 1.
Example 2:
Input: s = "10" Output: 1 Explanation: "10" corresponds to number 2 in their decimal representation. Step 1) 2 is even, divide by 2 and obtain 1.
Example 3:
Input: s = "1" Output: 0
Constraints:
1 <= s.length <= 500s consists of characters '0' or '1's[0] == '1'Problem Overview: A binary string represents a positive integer. Apply two rules until the number becomes 1: if the number is even, divide it by 2; if odd, add 1. The task is to count how many operations are required.
Approach 1: Simulation Based on Binary Operations (O(n) time, O(1) space)
Treat the input as a binary string and simulate the operations directly without converting it to an integer. Iterate from the rightmost bit toward the left while maintaining a carry that represents previous +1 operations. When the current bit plus carry is even, the operation is a divide-by-2 (move left). When it is odd, an add-1 occurs, which creates a carry and requires an extra step. Each bit is processed once, so the algorithm runs in O(n) time with constant extra space. This approach leverages simple rules of bit manipulation and avoids expensive large-number arithmetic.
The key insight: adding 1 to a binary number may propagate a carry through consecutive 1s. Instead of modifying the entire string repeatedly, track that carry logically while scanning. Every bit contributes either one step (division) or two steps (add then divide) depending on its effective value after carry.
Approach 2: Decimal Conversion and Simulation (O(n^2) time, O(n) space)
Convert the binary string to a decimal integer and simulate the rules directly: if the number is even, divide by 2; otherwise add 1. Repeat until the value becomes 1 while counting operations. The logic is straightforward and mirrors the problem statement exactly.
This method is easy to implement in languages with built-in big integers, but the integer can grow beyond standard limits. Each arithmetic operation on large numbers costs more than constant time, so the overall complexity becomes roughly O(n^2) where n is the binary length. The approach also uses O(n) space for the big integer representation. It relies more on numeric conversion than direct string processing.
Recommended for interviews: The binary simulation approach. Interviewers expect you to reason about binary behavior and carries instead of converting to decimal. Implementing the right-to-left scan shows strong understanding of binary arithmetic and keeps the complexity optimal at O(n) time with O(1) space.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulation Based on Binary Operations | O(n) | O(1) | Best general solution. Efficient for very long binary strings and commonly expected in interviews. |
| Decimal Conversion and Simulation | O(n^2) | O(n) | Quick to implement when big integers are available and input size is small. |