## DEV Community is a community of 700,720 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # Algorithms Problem Solving: Reduce to zero TK
Sharing knowledge https://leandrotk.github.io
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.

## Discussion (8) 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. 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.