# Number of Steps to Reduce a Number in Binary Representation to One
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one)
Canonical: https://scaleengineer.com/dsa/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** String
**Companies:** [Grab](https://scaleengineer.com/companies/grab), [Geico](https://scaleengineer.com/companies/geico)
---
## Problem
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 <= 500`
* `s` consists of characters '0' or '1'
* `s[0] == '1'`

# Approaches
## Simulation using BigInteger
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.
**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.
**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 `BigInteger` operations.; Higher memory usage as it needs to store the large number in a `BigInteger` object.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
*   Convert the input binary string `s` into a `java.math.BigInteger` object.
*   Initialize a `steps` counter to 0.
*   Create `BigInteger` constants for `ONE` and `TWO` for convenience.
*   Enter a loop that continues as long as the `BigInteger` value is not equal to `ONE`.
*   Inside the loop, check if the number is even or odd. A `BigInteger` is even if its least significant bit is 0. This can be checked using the `testBit(0)` method. If `testBit(0)` returns `false`, the number is even.
*   If the number is even, divide it by `TWO`.
*   If the number is odd, add `ONE` to it.
*   Increment the `steps` counter in each iteration.
*   Once the loop terminates (when the number becomes `ONE`), return the total `steps`.

## Simulation on a Mutable String
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.
**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.
**Pros:** More efficient than `BigInteger` in 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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
*   Create a `StringBuilder` from the input string `s` to allow for efficient modifications.
*   Initialize a `steps` counter 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 `steps` counter for each operation.
*   Return the total `steps` when the loop finishes.

## Optimized Single Pass from Right to Left
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.
**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`).
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
*   Initialize `steps = 0` and `carry = 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 the `carry` from 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 to `steps`. The 'add 1' operation creates a new carry, so we set `carry = 1`.
*   If `s.charAt(i) - '0' + carry` is 0 or 2: The number is effectively even. It requires one operation: divide by 2 (1 step). So, we add 1 to `steps`. The carry propagates if the sum was 2, so `carry` remains `1` if it was already `1` and the bit was `1`, otherwise it becomes `0`.
*   After the loop, we are left with the most significant bit `s[0]`, which is always '1'. If `carry` is 1, the remaining number is effectively `1 + carry = 2`. This requires one final step (division) to become 1. So, we add the final `carry` to `steps`.
*   Return the total `steps`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```