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

Date published: 2020-03-27

Category: Python

Subcategory: Beginner Algorithms

Tags: functions, loops, modulo, dictionaries

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

# 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

# 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

# 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

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

assert number_of_steps(8) == 4

In [3]:

assert number_of_steps(14) == 6

assert number_of_steps(14) == 6