minimum_steps_to_one.py

"""
YouTube Explanation: https://www.youtube.com/watch?v=f2xi3c1S95M

Given an integer n, return the minimum steps from n to 1

AVAILABLE STEPS:
 * Decrement by 1
 * if n is divisible by 2, divide by 2
 * if n is divisible by 3, divide by 3


Example 1: n = 10
10 -> 9 -> 3 -> 1
Result: 3 steps

Example 2: n = 15
15 -> 5 -> 4 -> 2 -> 1
Result: 4 steps

Example 3: n = 6
6 -> 2 -> 1
Result: 2 step
"""

from __future__ importannotations

__author__="Alexander Joslin"


defmin_steps_to_one(number: int) ->int:
"""
 Minimum steps to 1 implemented using tabulation.
 >>> min_steps_to_one(10)
 3
 >>> min_steps_to_one(15)
 4
 >>> min_steps_to_one(6)
 2

 :param number:
 :return int:
 """

ifnumber<=0:
msg=f"n must be greater than 0. Got n = {number}"
raiseValueError(msg)

table= [number+1] * (number+1)

# starting position
table[1] =0
foriinrange(1, number):
table[i+1] =min(table[i+1], table[i] +1)
# check if out of bounds
ifi*2<=number:
table[i*2] =min(table[i*2], table[i] +1)
# check if out of bounds
ifi*3<=number:
table[i*3] =min(table[i*3], table[i] +1)
returntable[number]


if__name__=="__main__":
importdoctest

doctest.testmod()