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

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

• Learning Python: From Zero to Hero
• Algorithms Problem Solving Series
• Big-O Notation For Coding Interviews and Beyond
• Learn Python from Scratch
• Learn Object-Oriented Programming in Python
• Data Structures in Python: An Interview Refresher
• Data Structures and Algorithms in Python
• Data Structures for Coding Interviews in Python
• One Month Python Course
• Big-O Notation For Coding Interviews and Beyond
• Learn Python from Scratch
• Learn Object-Oriented Programming in Python
• Data Structures in Python: An Interview Refresher
• Data Structures and Algorithms in Python
• Data Structures for Coding Interviews in Python
• One Month Python Course

Comments

[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)

[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.

[FriesischScott]

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

[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

[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.

[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.

[Joe Zack]

Ah ok, very cool! Thanks for explaining!

[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.