LeetCode Entry

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

29.05.2024 medium 2024 kotlin rust

Steps even/2, odd+1 to make binary s to 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/621

Problem TLDR

Steps even/2, odd+1 to make binary s to 1 #medium

Intuition

We can just implement what is asked recursively passing a new string each time. The more interesting and effective solution is to iterate from the end and try to count operations on the fly:

• calculate current and carry
• apply extra operation if current is odd and do extra increase for carry

Approach

Let’s minify the code using the math tricks.

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(1)\)

Code

    fun numSteps(s: String): Int {
        var carry = 0
        return (s.lastIndex downTo 1).sumOf { i ->
            val curr = s[i] - '0' + carry
            carry = curr / 2 + curr % 2
            1 + curr % 2
        } + carry
    }

    pub fn num_steps(s: String) -> i32 {
        let (mut carry, sb) = (0, s.as_bytes());
        (1..s.len()).rev().map(|i| {
            let curr = sb[i] as i32 - b'0' as i32 + carry;
            carry = curr / 2 + curr % 2;
            1 + curr % 2
        }).sum::<i32>() + carry
    }