iframe-proxy | Sunbelt Computer Software

History

66 lines (49 loc) · 1.32 KB

Raw

"""

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__ import annotations

__author__ = "Alexander Joslin"

def min_steps_to_one(number: int) -> int:

"""

Minimum steps to 1 implemented using tabulation.

>>> min_steps_to_one(10)

>>> min_steps_to_one(15)

>>> min_steps_to_one(6)

:param number:

:return int:

"""

if number <= 0:

msg = f"n must be greater than 0. Got n = {number}"

raise ValueError(msg)

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

# starting position

table[1] = 0

for i in range(1, number):

table[i + 1] = min(table[i + 1], table[i] + 1)

# check if out of bounds

if i * 2 <= number:

table[i * 2] = min(table[i * 2], table[i] + 1)

# check if out of bounds

if i * 3 <= number:

table[i * 3] = min(table[i * 3], table[i] + 1)

return table[number]

if __name__ == "__main__":

import doctest

doctest.testmod()

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

minimum_steps_to_one.py

Latest commit

History

minimum_steps_to_one.py

File metadata and controls