“This is the 15th time I have participated in the 2022 First Revision Challenge. For details, see: 2022 First Revision Challenge”

Number of operations to change a number to 0

Given a non-negative integer num, return the number of steps required to get it to 0. If the current number is even, you divide it by 2; Otherwise, subtract 1.

 

Example 1:

Input: num = 14 Output: 6 Explanation: Step 1) 14 is even. Divide by 2 to get 7. Step 2) 7 is odd. Subtract 1 to get 6. Step 3) 6 is even. Divide by 2 to get 3. Step 4) 3 is odd, subtract 1 to get 2. Step 5) 2 is even. Divide by 2 to get 1. Step 6) 1 is odd; subtract 1 to get 0.

Example 2:

Input: num = 8 Output: 4 Explanation: Step 1) 8 is even. Divide by 2 to get 4. Step 2) 4 is even. Divide by 2 to get 2. Step 3) 2 is even. Divide by 2 to get 1. Step 4) 1 is odd; subtract 1 to get 0.

Example 3:

Input: num = 123 Output: 12

 

Tip:

0 <= num <= 10^6

Iterative method

Iterative solution analysis

If num is an even integer, divide it by 2. If num is odd, subtract 1.

We can continue processing the condition through a while loop until num is 0.

Iterative solution is implemented step by step

Check whether num is 0. If num is 0, return result.

if(num === 0) return num
Copy the code

We set a count variable to count the number of operations that change the number to 0, initialized to 0.

let count = 0
Copy the code

Use a while loop to increment count by one each time it executes. If num % 2 is 0, divide by 2; if num % 2 is odd, subtract 1.

while (num) {
    if(num % 2= = =0){
        num = num / 2
    }else{
        num = num - 1
    }
    count++
}
Copy the code

Finally, return the number we counted, count


return count

Copy the code

Iterative solution complete code implementation

/ * * *@param {number} num
 * @return {number}* /
var numberOfSteps = function (num) {
    if(num === 0) return num
    let count = 0
    while (num) {
        if(num % 2= = =0){
            num = num / 2
        }else{
            num = num - 1
        }
        count++
    }
    return count
};
Copy the code

Bit operation + recursive solution

Bit operation + recursive analysis

If num is an even integer, divide it by 2. If num is odd, subtract 1.

We can continue processing the condition through a while loop until num is 0.

Bit operation + recursive solution step by step

Check whether num is 0. If num is 0, return result.

if(num === 0) return num
Copy the code

The first thing we can do is tell if it’s even by bitwise and theta

if ((num & 1) = =0) {}else{}Copy the code

When it is even we can divide by 2 by moving num >> 1 to the right in the bit operation,

if ((num & 1) = =0) {
    return 1 + numberOfSteps(num >> 1);
}
Copy the code

We subtract one when it’s odd

if ((num & 1) = =0) {
    return 1 + numberOfSteps(num >> 1);
}else {
    return 1 + numberOfSteps(num--); 
}
Copy the code

Bit operation + recursive solution complete code implementation

/ * * *@param {number} num
 * @return {number}* /
var numberOfSteps = function (num) {
  if (num == 0) return 0;
  if ((num & 1) = =0) {
    return 1 + numberOfSteps(num >> 1);
  } else {
    return 1+ numberOfSteps(num--); }};Copy the code