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'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.
C++
C#
Java
JavaScript
C
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).
C++
C#
Java
JavaScript
C
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.
| 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). |
Number of Steps to Reduce a Number in Binary Representation to One - Leetcode 1404 - Python • NeetCodeIO • 8,439 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