Number of Steps to Reduce a Number in Binary Representation to One
MedPrompt
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
1to 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 <= 500sconsists of characters '0' or '1's[0] == '1'
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the problem statement into code. Since the number represented by the binary string s can be very large (up to 2^500 - 1), we cannot use standard primitive data types like long. Java's java.math.BigInteger class is perfect for handling arithmetic on such large numbers.
Algorithm
- Convert the input binary string
sinto ajava.math.BigIntegerobject. - Initialize a
stepscounter to 0. - Create
BigIntegerconstants forONEandTWOfor convenience. - Enter a loop that continues as long as the
BigIntegervalue is not equal toONE. - Inside the loop, check if the number is even or odd. A
BigIntegeris even if its least significant bit is 0. This can be checked using thetestBit(0)method. IftestBit(0)returnsfalse, the number is even. - If the number is even, divide it by
TWO. - If the number is odd, add
ONEto it. - Increment the
stepscounter in each iteration. - Once the loop terminates (when the number becomes
ONE), return the totalsteps.
Walkthrough
The algorithm starts by converting the input binary string s into a BigInteger object. It then enters a loop that continues as long as the number is not equal to one. Inside the loop, it checks if the number is even or odd. If the number is even, it's divided by two. If it's odd, one is added to it. A counter is incremented for each step (either division or addition). The loop terminates when the number becomes one, and the total count of steps is returned.
import java.math.BigInteger; class Solution { public int numSteps(String s) { BigInteger num = new BigInteger(s, 2); final BigInteger ONE = BigInteger.ONE; final BigInteger TWO = new BigInteger("2"); int steps = 0; while (!num.equals(ONE)) { // testBit(0) checks the least significant bit. // If it's 0, the number is even. if (!num.testBit(0)) { num = num.divide(TWO); } else { num = num.add(ONE); } steps++; } return steps; }}Complexity
Time
O(N^2), where N is the length of the string `s`. The number of bits in the `BigInteger` is N. The number of steps in the reduction process is on the order of O(N). Each addition or division operation on an N-bit `BigInteger` takes O(N) time. Therefore, the total time complexity is O(N * N) = O(N^2).
Space
O(N), where N is the length of the string `s`. This is required to store the `BigInteger` object, which needs space proportional to the number of bits.
Trade-offs
Pros
Simple to understand and implement as it directly follows the problem description.
Robustly handles arbitrarily large numbers without risk of overflow.
Cons
Less efficient compared to other approaches due to the overhead of
BigIntegeroperations.Higher memory usage as it needs to store the large number in a
BigIntegerobject.
This approach avoids the overhead of BigInteger by performing the binary arithmetic directly on a mutable string representation, such as a StringBuilder. This is generally more efficient in practice than using BigInteger for this specific problem, as the operations are more tailored, although the asymptotic complexity remains the same.
Algorithm
- Create a
StringBuilderfrom the input stringsto allow for efficient modifications. - Initialize a
stepscounter to 0. - Loop as long as the
StringBuilder's length is greater than 1 (i.e., the number is not 1). - In each iteration, check the last character of the string.
- If the last character is '0' (even number), simulate division by 2 by removing the last character.
- If the last character is '1' (odd number), simulate adding 1. This involves finding the rightmost '0', flipping it to a '1', and flipping all subsequent '1's to '0's. If all characters are '1's, they all become '0's, and a new '1' is prepended.
- Increment the
stepscounter for each operation. - Return the total
stepswhen the loop finishes.
Walkthrough
We first convert the input string s into a StringBuilder to allow for efficient modifications. We loop until the string represents the number 1 (i.e., its content is "1"). In each iteration, we check the last character of the string. If it's '0', the number is even, and we simulate division by 2 by removing this character. If it's '1', the number is odd, and we simulate adding 1 by performing binary addition directly on the string's characters. We increment a step counter for each operation.
class Solution { public int numSteps(String s) { StringBuilder sb = new StringBuilder(s); int steps = 0; while (sb.length() > 1) { int lastIndex = sb.length() - 1; if (sb.charAt(lastIndex) == '0') { // Even number: divide by 2 (right shift) sb.deleteCharAt(lastIndex); } else { // Odd number: add 1 int i = lastIndex; while (i >= 0 && sb.charAt(i) == '1') { sb.setCharAt(i, '0'); i--; } if (i < 0) { // All were '1's, prepend a '1' sb.insert(0, '1'); } else { sb.setCharAt(i, '1'); } } steps++; } return steps; }}Complexity
Time
O(N^2), where N is the length of the string. The main loop runs O(N) times. Inside the loop, division by 2 (deleting the last character) is fast. However, adding 1 can take O(N) time in the worst case (e.g., for a string of all '1's), as we might need to scan and modify the entire string. This leads to a total time complexity of O(N^2).
Space
O(N) to store the `StringBuilder`, where N is the length of the input string.
Trade-offs
Pros
More efficient than
BigIntegerin practice due to avoiding its object creation and method call overhead.Works directly with the given data format.
Cons
Still has a quadratic worst-case time complexity.
Modifying the string in a loop, especially for the addition case, can be complex to implement correctly.
This is the most efficient approach. Instead of simulating the full operations on the entire number in each step, we can determine the total number of steps by making a single pass through the binary string from right to left. We can deduce the operations that would happen at each bit position by tracking a carry.
Algorithm
- Initialize
steps = 0andcarry = 0. - Iterate through the string from right to left, starting from the last character (
i = s.length() - 1) down to the second character (i = 1). - For each character
s[i], calculate the effective bit value by adding thecarryfrom the previous step. - If
s.charAt(i) - '0' + carry == 1: The number is effectively odd at this stage. An odd number requires two operations: add 1 (1 step) and then divide by 2 (1 step). So, we add 2 tosteps. The 'add 1' operation creates a new carry, so we setcarry = 1. - If
s.charAt(i) - '0' + carryis 0 or 2: The number is effectively even. It requires one operation: divide by 2 (1 step). So, we add 1 tosteps. The carry propagates if the sum was 2, socarryremains1if it was already1and the bit was1, otherwise it becomes0. - After the loop, we are left with the most significant bit
s[0], which is always '1'. Ifcarryis 1, the remaining number is effectively1 + carry = 2. This requires one final step (division) to become 1. So, we add the finalcarrytosteps. - Return the total
steps.
Walkthrough
We process the binary string from the least significant bit (rightmost) to the most significant bit (leftmost). We maintain a carry variable, initialized to 0, which represents the carry-over from adding 1 to the bits on the right. We iterate from the end of the string towards the beginning. For each bit, we consider its value plus the current carry. If the sum is 1, the number is odd, requiring 2 steps (add 1, then divide), and we set carry to 1. If the sum is 0 or 2, the number is even, requiring 1 step (divide), and the carry propagates. After the loop, if there's a final carry, it means the remaining number is 2, which needs one more step. This allows us to calculate the total steps in one pass.
class Solution { public int numSteps(String s) { int steps = 0; int carry = 0; // Iterate from the rightmost bit to the second bit (index 1) for (int i = s.length() - 1; i > 0; i--) { int bit = s.charAt(i) - '0'; if (bit + carry == 1) { // This is an odd number (...1). // Op 1: Add 1. It becomes ...0 with a carry. // Op 2: Divide by 2. // Total 2 steps. The new carry is 1. carry = 1; steps += 2; } else { // This is an even number (...0). // Op 1: Divide by 2. // Total 1 step. The carry propagates. steps += 1; } } // Finally, we are at the most significant bit (s[0] = '1'). // If carry is 1, the number is 1 + 1 = 2. One more step (division) is needed. // If carry is 0, the number is 1. We are done. return steps + carry; }}Complexity
Time
O(N), where N is the length of the string. We perform a single pass over the string.
Space
O(1), as we only use a few extra variables to store the state (`steps`, `carry`).
Trade-offs
Pros
Highly efficient with linear time complexity.
Constant space complexity, making it very memory-efficient.
Cons
The logic is less intuitive than direct simulation and requires careful reasoning about binary operations and carries.
Solutions
Solution
class Solution {public int numSteps(String s) { boolean carry = false; int ans = 0; for (int i = s.length() - 1; i > 0; --i) { char c = s.charAt(i); if (carry) { if (c == '0') { c = '1'; carry = false; } else { c = '0'; } } if (c == '1') { ++ans; carry = true; } ++ans; } if (carry) { ++ans; } return ans; }}class Solution {public: int numSteps(string s) { int ans = 0; bool carry = false; for (int i = s.size() - 1; i; --i) { char c = s[i]; if (carry) { if (c == '0') { c = '1'; carry = false; } else c = '0'; } if (c == '1') { ++ans; carry = true; } ++ans; } if (carry) ++ans; return ans; }};class Solution: def numSteps(self, s: str) -> int: carry = False ans = 0 for c in s[: 0: - 1]: if carry: if c == '0': c = '1' carry = False else: c = '0' if c == '1': ans += 1 carry = True ans += 1 if carry: ans += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.