DEV Community

loading...
Cover image for Solution: Number of Steps to Reduce a Number to Zero

Solution: Number of Steps to Reduce a Number to Zero

seanpgallivan profile image seanpgallivan ・2 min read

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.


Leetcode Problem #1342 (Easy): Number of Steps to Reduce a Number to Zero


Description:

Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.


Examples:

Example 1:
Input: nums = [1,2,3]
Output: [1,3,2]
Example 1:
Input: num = 14
Output: 6
Explanation: Step 1) 14 is even; divide by 2 and obtain 7.
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3.
Step 4) 3 is odd; subtract 1 and obtain 2.
Step 5) 2 is even; divide by 2 and obtain 1.
Step 6) 1 is odd; subtract 1 and obtain 0.
Example 2:
Input: num = 8
Output: 4
Explanation: Step 1) 8 is even; divide by 2 and obtain 4.
Step 2) 4 is even; divide by 2 and obtain 2.
Step 3) 2 is even; divide by 2 and obtain 1.
Step 4) 1 is odd; subtract 1 and obtain 0.
Example 3:
Input: num = 123
Output:* 12

Constraints:

  • 0 <= num <= 10^6

Idea:

For this problem, we just have to follow the directions: we can tell if num is odd by using modulo 2; num % 2 is 1 if num is odd, otherwise it's 0. Anytime num is odd, subtract 1 from num. Anytime num is even, divide num by 2.

While we do this, we can just increment our counter (ans) and then return it once num reaches 0.


Javascript Code:

The best result for the code below is 68ms / 37.1MB (beats 99% / 100%).

var numberOfSteps  = function(num) {
    let ans = 0
    for (; num; ans++)
        if (num % 2) num--
        else num /= 2
    return ans
};
Enter fullscreen mode Exit fullscreen mode

Python Code:

The best result for the code below is 24ms / 14.1MB (beats 96% / 89%).

class Solution:
    def numberOfSteps (self, num: int) -> int:
        ans = 0
        while num > 0:
            if num % 2: num -= 1
            else: num /= 2
            ans += 1
        return ans
Enter fullscreen mode Exit fullscreen mode

Java Code:

The best result for the code below is 0ms / 35.5MB (beats 100% / 95%).

class Solution {
    public int numberOfSteps (int num) {
        int ans = 0;
        for (; num > 0; ans++)
            if (num % 2 == 1) num--;
            else num /= 2;
        return ans;
    }
}
Enter fullscreen mode Exit fullscreen mode

C++ Code:

The best result for the code below is 0ms / 5.8MB (beats 100% / 85%).

class Solution {
public:
    int numberOfSteps (int num) {
        int ans = 0;
        for (; num > 0; ans++)
            if (num % 2 == 1) num--;
            else num /= 2;
        return ans;
    }
};
Enter fullscreen mode Exit fullscreen mode

Discussion (3)

pic
Editor guide
Collapse
nithish_13 profile image
Nithish Kumar

Hey hi, I cant understand what is happening on this line.
// for (; num; ans++)
Could u explain?

Collapse
seanpgallivan profile image
seanpgallivan Author

Sure!

The for loop declaration is broken up into three parts. The first part is an expression that's executed once at the very beginning of the loop. Usually it's used to initialize loop variables. Here, I'm using ans as the iterable, but I also want to be able to refer to it once the loop is over, so I have to initialize it outside the loop. Since I don't have any other loop variables to initialize, the first part is left blank.

The middle portion is the "while" conditional. Here, I want to continue looping while num > 0. Since 0 evaluates as falsy and any other number evaluates as truthy, I can simplify that conditional to just num, so that when num decrements to 0, it triggers an end to the loop.

The third part is more standard: it's an expression that will run at the end of each loop, before restarting the next iteration. In this case, it's a fairly standard variable increment.

Collapse
nithish_13 profile image
Nithish Kumar

Thanks a ton 😄