Number of Steps to Reduce a Number to Zero Leetcode Solution

Difficulty Level Easy
Frequently asked in Amazon Google HRT Microsoft
algorithms Bit Manipulation coding Interview interviewprep LeetCode LeetCodeSolutionsViews 4585

The problem Number of Steps to Reduce a Number to Zero Leetcode Solution states that given an integer. Find the minimum number of steps to convert the given integer to 0. You can perform either of the two steps, either subtract 1 or divide the integer by 2. The problem seems simple but before going through the solution, we will see a few examples.

Number of Steps to Reduce a Number to Zero Leetcode Solution

n = 14
6

Explanation: Minimum number of steps to reduce the given integer(=14) to 0 requires 6 steps. First, divide 14 by 2. Now we are left with 7. Then we subtract 1. The number we now have is 6. We divide again by 2. Then we subtract 1 three times to reduce the integer(=3) to 0.

8
4

Explanation: We use 3 divide and 1 subtraction operation to reduce 8 to 0. The first move reduces 8 to 4, then 4 to 2, 2 to 1. Then we simply subtract 1 from 1 to get 0.

Brute Force Approach for Number of Steps to Reduce a Number to Zero Leetcode Solution

The problem is pretty standard and has been asked several times in various tests. The brute force solution for the problem is not sufficient to solve the problem under the time limit. The brute force solution uses recursion for the solution. For each integer, since we have two possible operations. We perform both of them and then recursively call for the modified integer. The time complexity for the solution will be exponential thus is not efficient for large inputs. The solution when coded will result into runtime error because the numbers which contain decimal part will never be able to reduce to 0.

Optimized Approach for Number of Steps to Reduce a Number to Zero Leetcode Solution

The problem is one of the standard problems, which are very widely known. The problem can be easily solved if we subtract 1 only when we encounter an odd number. And divide the number by 2, when we get an even number. Thus the solution of the problem is dependent on the parity of the integer. Why do we divide from 2 when the number is even? Because it’s always better or equally fine to reduce the number by making it half than subtracting 1. Then why don’t we divide the odd numbers? Because then we will end up having decimal integers, which cannot be reduced to 0 using these two operations in any way.

Optimized code for Number of Steps to Reduce a Number to Zero Leetcode Solution

C++ Code

#include <bits/stdc++.h>
using namespace std;

int numberOfSteps (int num) {
    int cnt = 0;
    while(num){
        if(num&1)num--;
        else num/=2;
        cnt++;
    }
    return cnt;
}

int main(){
    cout<<numberOfSteps(14);
}

6

Java Code

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int numberOfSteps (int num) {
        int cnt = 0;
        while(num > 0){
            if(num%2 == 1)num--;
            else num/=2;
            cnt++;
        }
        return cnt;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    System.out.print(numberOfSteps(14));
  }
}
6

Complexity Analysis

Time Complexity

O(logN), because we divide the integer by 2 whenever we get an even number. Each odd number is then converted into even number by subtracting 1 from it. Thus the time complexity comes out to be logarithmic.

Space Complexity

O(1), because we used a single variable, that is constant space. Thus the space complexity is also constant.

Translate »