Python Beginner Algorithms Tutorial

# Number of Steps to Reduce a Number to Zero (via Leetcode)

This problem can be found on Leetcode.

Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, divide it by 2; otherwise, subtract one from it.

### Write out Test Cases¶

In [ ]:
# assert number_of_steps(8) == 4


To elaborate on test case above. Here are the steps:

1) num of 8 is even; divide by 2; num equals 4

2) num of 4 is even; divide by 2; num equals 2

3) num of 2 is even; divide by 2; num equals 1

4) num of 1 is odd; subtract 1; num equals 0

In :
# assert number_of_steps(14) == 6


To elaborate on test case above. Here are the steps:

1) num of 14 is even; divide by 2; num equals 7

2) num of 7 is odd; subtract 1; num equals 6

3) num of 6 is even; divide by 2; num equals 3

4) num of 3 is odd; subtract 1; num equals 2

5) num of 2 is even; divide by 2; num equals 1

6) num of 1 is odd; subtract 1; num equals 0

### Pseudocode¶

In [ ]:
# define function to take in num
# set a variable for count of steps
# while num is not equal to 0:
# if num is even:
# reassign num to be num divided by 2
# else:
# number is odd...
# reassign num to be num minus 1
# increment count of steps variable by 1
# return count of steps


My solution above is the simplest possible solution. I wouldn't worry about time or space complexity considerations here. Time complexity is roughly O(n/2) and space complexity is simply O(1) for the one variable created.

### Code¶

In :
def number_of_steps(num):
count_of_steps = 0
while num != 0:
if num % 2 == 0:
num /= 2
else:
# number is odd...
num -= 1
count_of_steps += 1
return count_of_steps


### Verify test cases¶

In :
assert number_of_steps(8) == 4

In :
assert number_of_steps(14) == 6