Number of Steps to Reduce a Number to Zero — Day 74(Python)

Photo by Lindsay Henwood on Unsplash

Today’s question is easy. I have taken this question from Leetcode’s daily coding challenge February edition.

1342. Number of Steps to Reduce a Number to Zero

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.

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

One of the ways to solve this problem is by checking how many times we have to divide the given number by 2. If we observe the example, we can see that whenever the division results in an odd number, the counter is incremented by 2, while for an even number the counter is incremented by 1. How can we check if the number is odd or even? Each time we divide the number by 2, we need to check the remainder. If we have a remainder, the number is odd else the number is even.

Let us look into the code snippet.

class StepsCounter:
    def numberOfSteps (self, num: int) -> int:
        counter = 0
        while(num > 1):
            if num%2 == 0:  
                counter += 1
            else:
                counter += 2
            num = num//2
        if num == 1:
            counter += 1
        return counter

Complexity analysis.

Time Complexity

Since each time we are dividing by 2, the time complexity is O(logN).

Space Complexity.

Since we are not using any extra data structure to store intermediate results, the space complexity is O(1).