loading...
Cover image for Algorithms Problem Solving: Reduce to zero

Algorithms Problem Solving: Reduce to zero

teekay profile image TK Originally published at leandrotk.github.io ・2 min read

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

Posted on by:

teekay profile

TK

@teekay

Sharing knowledge https://leandrotk.github.io/tk

Discussion

markdown guide
 

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)
 

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.

 

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

 

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

 

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.

 

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.

Ah ok, very cool! Thanks for explaining!

 

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.