# 26.02.2026 [1404. Number of Steps to Reduce a Number in Binary Representation to One]
Ops /2+1 to make 1 #medium #simulation
26.02.2026
1404. Number of Steps to Reduce a Number in Binary Representation to One medium blog post substack youtube
Join me on Telegram
Problem TLDR
Ops /2+1 to make 1 #medium #simulation
Intuition
Simulate the process, O(n^2) is accepted
Approach
to optimize propagate the carry to the next op instead of doing full +1 operation
Complexity
Time complexity: $$O(n)$$
Space complexity: $$O(1)$$
Code
// 10ms
fun numSteps(s: String) = s.lastIndexOf('1') +
(if (Regex("^10*$") in s) 0 else 2) + s.count {it<'1'}
// 0ms
pub fn num_steps(s: String) -> i32 {
let mut c = 0;
(1..s.len()).rev().map(|i| {
c += (s.as_bytes()[i] - b'0') as i32;
let r = 1 + c % 2; c = c/2+c%2; r
}).sum::<i32>() + c
}