Min Steps to Zero
easySave
Bit ManipulationMath
Given a non-negative integer n, return the minimum number of steps to reduce n to zero. In one step, you can either decrement n by 1 or, if n is even, divide n by 2.
Example 1
Input
[ 14 ]
Output
6
Explanation. Steps: 14 -> 7 -> 6 -> 3 -> 2 -> 1 -> 0. Total of 6 steps.
Example 2
Input
[ 8 ]
Output
4
Explanation. Steps to reduce to zero: 8 -> 4 -> 2 -> 1 -> 0.
Example 3
Input
[ 0 ]
Output
0
Explanation. Zero requires no steps to reduce to zero.
Example 4
Input
[ 1 ]
Output
1
Explanation. 1 => 0 in one step.
Follow-up: Can you implement another version using recursion?
Constraints:
Input will be a non-negative integer.
- Views
- 2