DEV Community

Cover image for Algorithms Problem Solving: Reduce to zero
TK
TK

Posted on • Originally published at leandrotk.github.io

Algorithms Problem Solving: Reduce to zero

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

Resources

Discussion (8)

Collapse
friesischscott profile image
FriesischScott

While this is a perfectly valid solution to the problem, this is a problem where recursion really shines and removes the need for a loop.

def reduce_number(num, counter=0):
    if num == 0:
        return counter

    if num % 2 == 0:
        return reduce_number(num / 2, counter + 1)
    else:
        return reduce_number(num - 1, counter + 1)
Collapse
thejoezack profile image
Joe Zack

The recursive solution is prettier, but it's not doing any less work and it ties up more memory unless your language supports tail recursion (python doesn't)

I try to avoid recursive solutions for problems like these unless the solution specifically needs back tracking.

Collapse
friesischscott profile image
FriesischScott

Never heard of tail recursion before. I'll look it up, thanks.

Collapse
theshadowfax profile image
Srujan Kumar

If you try writing that number in binary format and count the number of bits to make it zero would be the answer and the time complexity would be the length of binary string

Collapse
thejoezack profile image
Joe Zack

Sounds like a similar problem on leetcode: leetcode.com/problems/counting-bits/

I don't see how this helps though, am I missing something?

8 requires 4 bits (log2(8) + 1) and has an expected answer of 4, there are 4 digits in 8: a one and 3 zeroes

14 has an expected answer of 6, but it's also 4 bits (log2(16) + 1), 3 ones and a zero.

Collapse
theshadowfax profile image
Srujan Kumar

Hey imagine this solution as travelling a series if bits where travelling has a cost, for example travelling from 0 to 1 and 0 to 0 will cost you "1" and travelling from 1 to 1 will cost you "2" and travelling from 1 to 0 will also cost you "2" and if the last bit is 1 then add "1"
So 10110 will cost you 7.

Thread Thread
thejoezack profile image
Joe Zack

Ah ok, very cool! Thanks for explaining!

Collapse
friesischscott profile image
FriesischScott

Can you please explain what you mean by count the number of bits to make it zero? I like the idea but I can't figure out how to go from 1110 to 6 or 1000 to 4 like in the example.