Leetcode 1342: Number of Steps to Reduce a Number to Zero

This problem asks us to find the number of operations to reduce the number to 0 given a simple algorithm describing what operation to do in each case.

Problem statement

This time, I commented the code on the solution, it should be clear enough on its own, but let me know if you have any questions.

class Solution {
    public int numberOfSteps(int num) {
        // we could do it iteratively, 
        // but it is somewhat more elegant to use recursion here, 
        // as the numbers are not too big (int), 
        // so assuming only 32 recursive calls at most.
        
        // base case, if num is 0 return 0, if num is 1 return 1
        if (num < 2) {
            return num;
        }
        
        // recursive case, if num is odd, do -1 and divide 
        // by two then recurse (2 ops),
        // if even, only divide by 2 and recurse (1 op)
        // note 1: num >> 1 takes care of both cases 
        // since it is truncated division by 2.
        // note 2: num % 2 == 1 is the same as (num & 1) == 1, 
        // I don't have a personal preference for either.
        return numberOfSteps(num >> 1) + (((num & 1) == 1) ? 2 : 1);
    }
}

Time and space taken for submission are 0ms and 36.4MB respectively.

Happy coding!

What’s next:

• Checkout the solution for another problem: Minimum falling path sum
• Contact me: poitevinpm@gmail.com
• Looking to interview for a software engineer position? Contact me :)