007.md

1342. Number of Steps to Reduce a Number to Zero

Difficulty: 🟢 Easy

Given an integer num, return the number of steps to reduce it to zero. In one step, 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: 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 <= 106

Solutions

Simple O(log n) solution

Python3

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

GO

func numberOfSteps(num int) int {
   steps := 0
   for num > 0 {
       if num%2 == 0 {
           num = num/2
       } else {
           num = num - 1
       }
       steps++
   } 
   return steps
}

The given solution solves the problem by iteratively reducing the number num to zero. It uses a variable steps to keep track of the number of steps taken. The algorithm performs the following steps:

1. Initialize steps to 0.
2. Enter a while loop that continues as long as num is not zero.
3. Inside the while loop, check if num is odd by using the condition num % 2. If it is odd, subtract 1 from num.
4. If num is even, divide it by 2 using the floor division operator //.
5. Increment steps by 1.
6. Repeat steps 3-5 until num becomes zero.
7. Return the value of steps.

Complexity Analysis

The time complexity of this algorithm is O(log num) because in each step, the value of num is either divided by 2 or decremented by 1. The number of steps required to reduce num to zero is proportional to the number of times it can be divided by 2.

The space complexity of the algorithm is O(1) since it uses a constant amount of extra space to store the variable steps.

Summary

The given solution calculates the number of steps required to reduce a given integer num to zero by performing the required operations in an iterative manner. The algorithm has a time complexity of O(log num) and a space complexity of O(1), making it efficient for the given constraints.

NB: If you want to get community points please suggest solutions in other languages as merge requests.