LeetCode Entry

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

26.02.2026 medium 2026 kotlin rust

Ops /2+1 to make 1

1404. Number of Steps to Reduce a Number in Binary Representation to One medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1281

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
    }