down_to_zero_ii.py

# source: https://www.hackerrank.com/challenges/down-to-zero-ii

#!/bin/python3

import os
import sys

MAX_N = 10 ** 6

# list of values by index, index corresponds to # of steps
PRECOMPUTED_LIST = list(range(MAX_N + 1))

for i in range(2, MAX_N + 1):
    curr_val = PRECOMPUTED_LIST[i]
    prev_val = PRECOMPUTED_LIST[i - 1]

    # check if prev_val +1 is better
    if curr_val > prev_val + 1:
        PRECOMPUTED_LIST[i] = prev_val + 1 # set curr_val to prev_val + 1
        curr_val = PRECOMPUTED_LIST[i] # resetting curr_val

    # update all instances where i is the max divisor (includes self)
    for j in range(2, i + 1):
        multiple = i * j
        if multiple > MAX_N: # if multiple us out of range...
            break

        init_val = PRECOMPUTED_LIST[multiple]

        # if initial value at the multiple is more than current + 1...
        if init_val > curr_val + 1:
            # change value to curr_val + 1
            PRECOMPUTED_LIST[multiple] = curr_val + 1

def downToZero(n, PRECOMPUTED_LIST):
    if n <= 3:
        return n

    return PRECOMPUTED_LIST[n] # O(1) 
    

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    q = int(input())

    for q_itr in range(q):
        n = int(input())

        result = downToZero(n, PRECOMPUTED_LIST)

        fptr.write(str(result) + '\n')

    fptr.close()