CODEWITHSUNDEEP
pythonrecursiondynamic-programming
Ben10101
Ben10101

Reputation: 11

Primitive Calculator - Dynamic & Recursive approach

I have tried to solve the Primitive calculator problem with dynamic and recursive approach , works fine for smaller inputs but taking long time for larger inputs (eg: 96234) .

You are given a primitive calculator that can perform the following three operations with the current number 𝑥: multiply 𝑥 by 2, multiply 𝑥 by 3, or add 1 to 𝑥. Your goal is given a positive integer 𝑛, find the minimum number of operations needed to obtain the number 𝑛 starting from the number 1.

import sys
def optimal_sequence(n,memo={}):
    
    
    if n in memo:
        return memo[n]
    if (n==1):
        return 0
    c1 = 1+optimal_sequence(n-1,memo)
        
    c2 = float('inf')
    if n % 2 == 0  :
        c2 = 1+optimal_sequence(n // 2,memo)
        
    c3 = float('inf')
    if n % 3 == 0 :
        c3 = 1+optimal_sequence(n // 3,memo)
    
    c = min(c1,c2,c3)
    memo[n] = c
    
    return c

input = sys.stdin.read()
n = int(input)
sequence = optimal_sequence(n)
print(sequence)  # Only printing optimal no. of operations

Can anyone point out what is wrong in recursive solution as it works fine by using for loop.

Upvotes: 1

Views: 357

Answers (1)

Chris Doyle
Chris Doyle

Reputation: 11992

There are a few things to consider here. The first is that you always check if you can subtract 1 away from n. This is always going to be true until n is 1. therefor with a number like 12. You will end up taking 1 away first, then calling the function again with n=11, then n=10, then n=9 etc......only once you have resolved how many steps it will take to resolve using the -1 method (in this case c1 will be 11) you then try for c2.

So for c2 you then half 12, then call the function which will start with the -1 again so you end up with n=12, n=6, n=5, n=4...etc. Even though you have n in the memo you still spend a lot of wasted time on function calls.

Instead you probably want to just shrink the problem space as fast as possible. So start with the rule that will reduce n the most. I.E divide by 3, if that doesnt work then divide by 2, only if neither of the first two worked then subtract 1.

With this method you dont even need to track n as n will always be getting smaller so there is no need to have a memo dict tracking the results.

from time import time


def optimal_sequence(n):
    if n == 1:
        return 0
    elif n % 3 == 0:
        c = optimal_sequence(n // 3)
    elif n % 2 == 0:
        c = optimal_sequence(n // 2)
    else:
        c = optimal_sequence(n - 1)
    return 1 + c


n = int(input("Enter a value for N: "))
start = time()
sequence = optimal_sequence(n)
end = time()
print(f"{sequence=} took {end - start} seconds")

also input is a python function to read from teh terminal you dont need to uses stdin

OUTPUT

Enter a value for N: 96234
sequence=15 took 0.0 seconds

Upvotes: 0

Related Questions