Explaining Leetcode’s Number of Steps to Reduce a Number to Zero Problem (JavaScript)

3 min readMar 30, 2020

This is another “easy” problem that was particularly annoying to me. Maybe precisely because it seems so easy.

The problem asks us to count how many steps we’d have to take to reduce a non-negative integer to zero by doing 1 of two steps:

Dividing by two if it’s even, or
Subtracting one, then dividing by two if it’s odd

Pretty simple. But as typical with code, many ways to do it. Here’s my first pass approach that came from intuition.

To me, while loops come to mind first with this kind of problem. My brain think, “I need to do X, while this is true”, and that’s exactly what a while loop does. The this in this case is while the number given to us is greater than 0 (i.e. the whole non-negative integer part of the problem).

The second possible solution that came to mind almost as quickly was recursion. But that will be the subject of another post.

We first create a variable to count our steps. Then, while our given integer is greater than 0, we do the steps that the instructions gave us. The key part that may not be as obvious is that we have to nest those instructions inside a conditional (e.g if/else) in order for the code to know when to execute it.

Here’s what the code looks like:

function numberOfSteps(num) {
  let steps = 0;while (num > 0) {
    if (num % 2 === 0) {
      num /= 2;
      steps++;
    } else {
      num--;
      steps++;
    }
  }
  return steps;
}

If we run this with the example given, where num = 14, these are the steps taken by this program:

Create a steps variable an initialize it with a value of 0.
Is 14 greater than 0? Of course, so we enter the loop
If we divide 14 by 2, do we get a remainder of 0? We do, so this condition evaluates to true, and we execute the following block by dividing it by 2 (resulting in 7), and incrementing our steps variable to 1.
Now num is 7, and still greater than 0, so we enter the loop again.
If we divide 7 by 2, do we get a remainder of 0? Nope, so we ignore this.
Next we have to subtract 1 from 7 resulting in 6, and increment our steps counter to 2.
Now num is 6, and still greater than 0, so we enter the loop again.
If we divide 6 by 2, do we get a remainder of 0? We do, so this condition evaluates to true, and we execute the following block by dividing it by 2 (resulting in 3), and incrementing our steps counter to 3.
Now num is 3, and still greater than 0, so we enter the loop again.
If we divide 3 by 2, do we get a remainder of 0? Nope, so we ignore this.
Next we have to subtract 1 from 3 resulting in 2, and increment our steps counter to 4.
Now num is 2, and still greater than 0, so we enter the loop again.
If we divide 2 by 2, do we get a remainder of 0? We do, so this condition evaluates to true, and we execute the following block by dividing it by 2 (resulting in 1), and incrementing our steps counter to 5.
Now num is 1, and still greater than 0, so we enter the loop again.
If we divide 1 by 2, do we get a remainder of 0? Negative Ghost Rider, so we ignore this.
Next we have to subtract 1 from 1 resulting in 0, and increment our steps counter to 6.
Now num is 0. Is 0 greater than 0? It is not, they’re the same, so the while loop stops execution and the program returns steps, which as this point is 6.

Bonus concept: this code executes in O(n) time, as it goes through each of these steps, as many times as n is, and increases as n increases.

Thanks for reading!

And remember: grit > talent.

Explaining Leetcode’s Number of Steps to Reduce a Number to Zero Problem (JavaScript)

Written by Saul Feliz