LeetCode Challenge #2: Number of Steps to Reduce a Number to Zero

Subscribe to my newsletter and never miss my upcoming articles

Problem statement:

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

Step-by-Step Solution

Identify Patterns After reading the problem and examples, we can observe 3 things:

  1. The problem output is an integer that increases every time we perform an operation on num.
  2. The code has to keep reducing num until it is zero.
  3. We have to divide num by 2 if it's even and subtract by 1 if it's odd.

Write the Pseudocode So let's try writing a solution for this problem without code:

  1. Initialize the output integer called steps which increases every time num gets divided or subtracted
  2. Have a continous loop to reduce num if it is greater than 0.
  3. In the loop, check if num is even or odd. If it is even, divide it by 2. Else, subtract it by 1.
  4. Remember to increase steps by 1 every time num is divided or subtracted in the loop.
  5. Finally, at the end of the loop, return the output steps.

Let's get coding! Now, we can write the Java code as follows:

class Solution {
    public int numberOfSteps (int num) {

        //Initialize step count to 0.
        int steps=0;

        //the loop keeps executing while num is greater than 0
        while(num > 0){
            //Use the % (modulo) operator to check if number is odd or even
            //if num is even, divide by 2. 
            if(num % 2 == 0){
                num = num/2;
            }else{
                num--; //else, num is odd so subtract 1
            }
           steps++; //rmb to add the steps by 1
        }
        //once num is 0, the loop stops and returns the output steps
        return steps;
    }
}

Conclusion

This problem may be difficult for beginners who are not yet familiar with the % (modulo) operator. This operator finds the remainder of a division between 2 numbers. For example, in this problem, we take num % 2, which means we are trying to get the remainder of num when it is divided by 2. If it is even, it will have no remainder (i.e. 0). But if it is odd, we will get a remainder of 1. Hence, using this operator, we can easily determine whether a number is odd or even. Practice more modulo-related questions and it will be easier to understand! Hope this tutorial helps!

No Comments Yet