Number of steps to reduce a number in binary representation to one

String Bit Manipulation Simulation

63.7% acceptance

Feb 25, 2026

1733

101

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn num_steps(s: String) -> i32 {
    let bs: Vec<u8> = s.bytes().map(|b| b - b'0').collect();
    let n = bs.len();
    let mut steps = 0;
    let mut carry = 0u8;
    for i in (1..n).rev() {
      let bit = bs[i] + carry;
      if bit % 2 == 1 {
        carry = 1;
        steps += 2;
      } else {
        steps += 1;
        carry = bit / 2;
      }
    }
    steps + carry as i32
  }
}