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.
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 <= 106In this approach, we use a loop to repetitively apply the given conditions on the number. If the number is even, divide it by 2, and if odd, subtract 1. We count and return the number of operations needed to reduce the number to zero.
The function numberOfSteps iteratively checks if the number is even or odd, performs the respective operation, and increments the step counter until the number reduces to zero. The result is printed in the main function.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log n) where n is the initial number.
Space Complexity: O(1), since no additional space is used.
This approach uses recursion to handle the problem. The function calls itself with the same logical conditions: divide by 2 for even or subtract 1 for odd, until the base case of zero is reached. It accumulates the count of steps through recursive calls.
This recursive solution involves the function calling itself while reducing the number based on its parity until it terminates on zero, accumulating step count in the process.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log n)
Space Complexity: O(log n), considering function call stack for recursion.
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(log n) where n is the initial number. |
| Recursive Approach | Time Complexity: O(log n) |
Number of Steps to Reduce a Number in Binary Representation to One - Leetcode 1404 - Python • NeetCodeIO • 8,439 views views
Watch 9 more video solutions →Practice Number of Steps to Reduce a Number to Zero with our built-in code editor and test cases.
Practice on FleetCode