Home

Reduce to zero

Light in the dark Photo by Jeremy Perkins

This post is part of the Algorithms Problem Solving series.

Problem description

This is the Number of Steps to Reduce a Number to Zero problem. The description looks like this:

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.

Examples

Input: num = 14
Output: 6

Input: num = 8
Output: 4

Solution

The solution is to do the subtraction or the division until the number is zero.

We can do this by using a while loop. If it is zero, the loop will stop. If it is not, keep the calculation.

def reduce_number(num):
    if num % 2 == 0:
        return num / 2
    else:
        return num - 1

def number_of_steps(num):
    counter = 0

    while num:
        counter += 1
        num = reduce_number(num)

    return counter

I also add a separate function called reduce_number to be responsible to the calculation.

Resources

Patreon Become a Patron Coffee icon Buy me a coffee