Number of Steps to Reduce a Number in Binary Representation to One

Medium
543.

Number of Steps to Reduce a Number in Binary Representation to One

Number of Steps to Reduce a Number in Binary Representation to One is a medium coding problem on strings, bit manipulation and simulation, asked in Amazon and Google interviews.

You are given the binary representation of an integer as a string s.

Reduce it to 1 using these steps:

  • If the number is even, divide it by 2.
  • If it is odd, add 1 to it.

Return the number of steps required. The input is guaranteed to have no leading zeros other than the number "1" itself.

Example 1

Input
s = "1101"
Output
6
Explanation
13 → 14 → 7 → 8 → 4 → 2 → 1.

Example 2

Input
s = "10"
Output
1
Explanation
2 → 1.

Example 3

Input
s = "1"
Output
0

Constraints

  • 1 <= s.length <= 500
  • s consists of characters '0' and '1'.
  • s[0] is '1'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var numSteps = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Steps to Reduce a Number in Binary Representation to One

Number of Steps to Reduce a Number in Binary Representation to One solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Number of Steps to Reduce a Number in Binary Representation to One is a medium coding problem on strings, bit manipulation and simulation, asked in Amazon and Google interviews.

Problem statement

You are given the binary representation of an integer as a string s.

Reduce it to 1 using these steps:

  • If the number is even, divide it by 2.
  • If it is odd, add 1 to it.

Return the number of steps required. The input is guaranteed to have no leading zeros other than the number "1" itself.

Example 1

Input: s = "1101"
Output: 6
Explanation: 13 → 14 → 7 → 8 → 4 → 2 → 1.

Example 2

Input: s = "10"
Output: 1
Explanation: 2 → 1.

Example 3

Input: s = "1"
Output: 0

Constraints

  • 1 <= s.length <= 500
  • s consists of characters '0' and '1'.
  • s[0] is '1'.

Hints for Number of Steps to Reduce a Number in Binary Representation to One

  1. Hint 1

    The number can be 500 bits long, so it will not fit in any built-in integer type.

  2. Hint 2

    Work on the bit string from the least significant end, carrying as in binary addition.

  3. Hint 3

    A 0 bit costs one step (a division); a 1 bit costs two (an addition then a division) and sets a carry.

How to solve Number of Steps to Reduce a Number in Binary Representation to One

Process the bits right to left with a carry. Each bit's cost is determined locally: dividing shifts the string right by one, and adding 1 to an odd number propagates a carry leftward.

Approach

  1. Start with steps = 0 and carry = 0, and walk i from the last index down to index 1.
  2. Let bit = s[i] + carry. If bit == 1 the number is odd: add 1 (one step) then divide (another step), so add 2 to steps and set carry = 1.
  3. Otherwise the number is even: add 1 step for the division, and set carry = 1 only if bit == 2 (a 1 plus an incoming carry).
  4. After the loop, add carry — a final carry means the leading 1 became 10, which needs one more division.

Why it works

Dividing by two is exactly dropping the last bit, so sweeping right to left visits the bits in the order the algorithm consumes them. The carry encodes the pending +1 from the most recent odd step, which is precisely how binary addition propagates.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Parsing the string into an integer overflows for anything past 64 bits.
  • Forgetting the trailing + carry undercounts whenever the final carry reaches the leading bit.
  • The loop must stop at index 1, not 0 — the leading bit is handled by the carry term.

Reference solution

Python

def numSteps(s: str) -> int:
    steps = 0
    carry = 0
    for i in range(len(s) - 1, 0, -1):
        bit = int(s[i]) + carry
        if bit == 1:
            steps += 2
            carry = 1
        else:
            steps += 1
            carry = 1 if bit == 2 else 0
    return steps + carry

Java

public static int numSteps(String s) {
    int steps = 0, carry = 0;
    for (int i = s.length() - 1; i >= 1; i--) {
        int bit = (s.charAt(i) - '0') + carry;
        if (bit == 1) {
            steps += 2;
            carry = 1;
        } else {
            steps += 1;
            carry = bit == 2 ? 1 : 0;
        }
    }
    return steps + carry;
}

C++

int numSteps(string s) {
    int steps = 0, carry = 0;
    for (int i = (int) s.size() - 1; i >= 1; i--) {
        int bit = (s[i] - '0') + carry;
        if (bit == 1) {
            steps += 2;
            carry = 1;
        } else {
            steps += 1;
            carry = bit == 2 ? 1 : 0;
        }
    }
    return steps + carry;
}

JavaScript

var numSteps = function(s) {
    let steps = 0, carry = 0;
    for (let i = s.length - 1; i >= 1; i--) {
        const bit = Number(s.charAt(i)) + carry;
        if (bit === 1) {
            steps += 2;
            carry = 1;
        } else {
            steps += 1;
            carry = bit === 2 ? 1 : 0;
        }
    }
    return steps + carry;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Bit Manipulation