Number of Steps to Reduce a Binary Number to One
Process the binary string from LSB; each set bit triggers an add (carry chain) that may cascade — simulate with a carry flag.
Problem#
Given a binary string s, count steps to reduce it to "1". Each step: if even (last bit 0), divide by 2 (shift right); if odd, add 1.
Examples#
"1101"→6"10"→1
Constraints#
1 <= s.length <= 500, no leading zeros (except"0").
Approach#
Walk right-to-left starting from index n - 1. For each bit (except the leading 1), bit + carry determines the step count: 1 step (shift) if effectively 0, 2 steps (add then shift) if effectively 1. Propagate carry on the second case.
Solution#
class Solution {public: int numSteps(string s) { int steps = 0, carry = 0; for (int i = s.size() - 1; i >= 1; --i) { int bit = (s[i] - '0') + carry; if (bit == 1) { // odd: +1 then shift = 2 steps, carry next steps += 2; carry = 1; } else { // even: shift = 1 step steps += 1; carry = bit / 2; } } return steps + carry; // leading 1 absorbs final carry }};func numSteps(s string) int { steps, carry := 0, 0 for i := len(s) - 1; i >= 1; i-- { bit := int(s[i]-'0') + carry if bit == 1 { steps += 2 carry = 1 } else { steps += 1 carry = bit / 2 } } return steps + carry}class Solution: def numSteps(self, 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 = bit // 2 return steps + carryfunction numSteps(s) { let steps = 0, carry = 0; for (let i = s.length - 1; i >= 1; i--) { const bit = (s.charCodeAt(i) - 48) + carry; if (bit === 1) { steps += 2; carry = 1; } else { steps += 1; carry = bit >> 1; } } return steps + carry;}class Solution { public 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; } } return steps + carry; }}function numSteps(s: string): number { let steps = 0, carry = 0; for (let i = s.length - 1; i >= 1; i--) { const bit = (s.charCodeAt(i) - 48) + carry; if (bit === 1) { steps += 2; carry = 1; } else { steps += 1; carry = bit >> 1; } } return steps + carry;}Editorial#
The key insight: each lower bit is independent given the running carry. A 0 bit contributes 1 step (shift). A 1 bit with no carry contributes 2 steps (add 1 makes it even-then-shift) and propagates a carry to the next bit. The leading 1 gets +1 if there’s a leftover carry (becomes “10” → “1”, one more shift).
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#