1342. Number of Steps to Reduce a Number to Zero.md

1342. Number of Steps to Reduce a Number to Zero

1. 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.

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

2. Solutions

Solution 1: Language: C Normal Brute Force - No Beauty 😡

• Thursday, 29 April, 2021
• Time Complexity: $O(\log n)$
• Space Complexity: $O(1)$
• Runtime: 0 ms, faster than 100.00% of C online submissions for Number of Steps to Reduce a Number to Zero.
• Memory Usage: 5.5 MB, less than 66.45% of C online submissions for Number of Steps to Reduce a Number to Zero.

int numberOfSteps(int num) {
    int counter = 0;
    while (num > 0) {
        if (num % 2 == 0) {
            num /= 2;
        } else {
            num -= 1;
        }
        counter += 1;
    }
    return counter;
}

Solution 2: Language: C ❗️ Bit Operation - But No Codes 😭

I could only put my ideas here with no codes. For each even number, we divide it by 2; and for each odd number, we subtract it by 1.

So when we are doing the bit operation, we could calculate the total number of 1's in num, which means subtraction times. Then we add it to the length of digits in binary, which means the times of division. However, if num is not equal to zero, we also need to subtract one because we calculate the first 1's twice.