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

medium bit manipulation binary carry greedy

Problem

Given the binary representation of an integer as a string s, return the number of steps to reduce it to 1 under these rules: if the current number is even you must divide it by 2; if it is odd you must add 1 to it. It is guaranteed that 1 is always reachable.

Inputs = "1101"

Output6

13 → 14 → 7 → 8 → 4 → 2 → 1 takes 6 steps (add, halve, add, halve, halve, halve).

Inputs = "10"

Output1

2 is even, divide by 2 to reach 1 in a single step.

s (binary string, leading 1)

def num_steps(s):
    steps, carry = 0, 0
    for i in range(len(s) - 1, 0, -1):
        bit = int(s[i]) + carry
        if bit == 1:            # odd: add 1, then divide
            steps += 2
            carry = 1
        else:                   # even: just divide
            steps += 1
            carry = bit // 2
    return steps + carry        # absorb leading bit + carry

function numSteps(s) {
  let steps = 0, carry = 0;
  for (let i = s.length - 1; i > 0; i--) {
    const bit = (s[i] - 0) + carry;
    if (bit === 1) {          // odd: add 1, then divide
      steps += 2;
      carry = 1;
    } else {                  // even: just divide
      steps += 1;
      carry = bit >> 1;
    }
  }
  return steps + carry;       // absorb leading bit + carry
}

int numSteps(String s) {
    int steps = 0, carry = 0;
    for (int i = s.length() - 1; i > 0; i--) {
        int bit = (s.charAt(i) - '0') + carry;
        if (bit == 1) {        // odd: add 1, then divide
            steps += 2;
            carry = 1;
        } else {               // even: just divide
            steps += 1;
            carry = bit >> 1;
        }
    }
    return steps + carry;      // absorb leading bit + carry
}

int numSteps(string s) {
    int steps = 0, carry = 0;
    for (int i = (int)s.size() - 1; i > 0; i--) {
        int bit = (s[i] - '0') + carry;
        if (bit == 1) {        // odd: add 1, then divide
            steps += 2;
            carry = 1;
        } else {               // even: just divide
            steps += 1;
            carry = bit >> 1;
        }
    }
    return steps + carry;      // absorb leading bit + carry
}

Explanation

Naively, we would convert the whole string to a big integer and repeatedly add 1 or halve. That works but the number can have up to 500 bits. Instead we simulate the process directly on the bits, scanning from the least significant bit to the most significant, carrying any overflow as we go.

Dividing by 2 just drops the rightmost bit, so we sweep right-to-left over indices len-1 down to 1, treating each position as the current last bit. A running carry captures the +1 that may have spilled in from the position before it.

At each position the effective value is bit = digit + carry. If bit == 1 the number is odd: we add 1 (one step) which makes it even and creates a carry, then divide (a second step) — so steps += 2 and carry = 1. Otherwise the value is even (0 or 2): we just divide (one step), steps += 1, and pass along carry = bit / 2 (which is 0 for a 0 and 1 for a 2).

After the loop, only the leading 1 plus any pending carry remains. If carry is 0 the value is already 1, costing nothing; if carry is 1 the value is 2 and needs one final divide. Either way the extra cost is exactly carry, so the answer is steps + carry.

Example "1101" (13): the last bit is odd → +2 steps, carry 1; next bit becomes 2 → +1 step, carry 1; next becomes 2 → +1 step, carry 1; the leading bit plus carry adds 2 more → total 6.

Time: O(n) Space: O(1)