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.
This approach involves simulating the reduction steps performed directly on the binary number string. We traverse the binary string backwards, simulating each step based on whether the current number is odd or even. Additionally, whenever we encounter a carry after incrementing an odd number, we propagate the carry to handle the necessary binary addition.
This Python function iterates through the binary string from the least significant bit towards the most significant bit. It checks the parity of the current digit plus any existing carry. If the sum is even, this implies the number is even and a division takes place (1 step). If the sum is odd, an addition and subsequent division occur (2 steps). The carry represents binary addition's overflow, simulating the bit handling required.
Time Complexity: O(n), where n is the length of the string s.
Space Complexity: O(1), only a constant amount of extra space is used.
Convert the binary representation to a decimal integer, then simulate the operations using intuitive arithmetic operations. This approach avoids character-level string manipulations.
This implementation converts the binary input to a decimal integer using Python's base conversion. Then the function reduces the number using arithmetic operations analogous to the original rules (dividing when even or incrementing plus dividing when odd).
Time Complexity: O(n) for initial conversion, O(log m) for operations (where m is the integer value).
Space Complexity: O(1), after input conversion.
We simulate operations 1 and 2, while maintaining a carry carry to indicate whether there is a current carry. Initially, carry = false.
We traverse the string s from the end toward the beginning:
carry is true, the current bit c needs to be incremented by 1. If c is 0, it becomes 1 after adding 1, and carry becomes false; if c is 1, it becomes 0 after adding 1, and carry remains true.c is 1, we need to perform operation 1, i.e., add 1, and carry becomes true.c is 0, so we need to perform operation 2, i.e., divide by 2.After the traversal, if carry is still true, we need to perform operation 1 one more time.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Simulation Based on Binary Operations | Time Complexity: O(n), where n is the length of the string s. |
| Approach 2: Decimal Conversion and Simulation | Time Complexity: O(n) for initial conversion, O(log m) for operations (where m is the integer value). |
| Simulation | — |
| 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. |
Number of Steps to Reduce a Number in Binary Representation to One | 2 Approaches | Leetcode 1404 • codestorywithMIK • 13,171 views views
Watch 9 more video solutions →Practice Number of Steps to Reduce a Number in Binary Representation to One with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor