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 [4]:
# 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 [1]:
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 [2]:
assert number_of_steps(8) == 4
In [3]:
assert number_of_steps(14) == 6