Arithematic.py

MAX = 999999999


def get_min(a, b, c, index):
    if a <=b and a <=c:
        return a, index -1
    if b <=a and b <= c:
        return b, index // 2
    if c <= a and c <= b:
        return c, index // 3

def getCost(n):
    cost = [-1] * (n+1)
    cost [1] = 0
    cost [2] = 1
    cost [3] = 1
    prevIndexLst = [0] * (n+1)
    prevIndexLst[1]= 0
    prevIndexLst[2]= 1
    prevIndexLst[3]= 1
    
    for i in range(4, n+1):
        possible1 = cost[i-1]
        possible2 = MAX
        possible3 = MAX
        
        if i%3 == 0:
            possible3 = cost[i//3]
        if i%2 == 0:
            possible2 = cost[i//2]

        
        minCost, prevIndex = get_min(possible1, possible2, possible3, i)
        cost[i] = minCost + 1
        prevIndexLst[i]= prevIndex
        # print (i, possible1, possible2, possible3, cost[i], "|", prevIndex)
    for i in range(len(prevIndexLst)):
        print(i, ":", prevIndexLst[i])
    return cost[n], prevIndexLst



if __name__ == "__main__":
    
    n = 15
    
    minCost, prevIndexLst = getCost(n)
    index = n
    print(minCost)
    while(index != 1):
        print(prevIndexLst[index])
        index = prevIndexLst[index]