Minimum Steps To 1

Given a positive integer 'n', find and return the minimum number of steps that 'n' has to take to get reduced to 1. You can perform any one of the following 3 steps:

1. Subtract 1 from it. (n = n - ­1)
2. If n is divisible by 2, divide by 2.( if n % 2 == 0, then n = n / 2)
3. If n is divisible by 3, divide by 3. (if n % 3 == 0, then n = n / 3)

Input format :

> The first and the only line of input contains an integer value, 'n'.

Output format :

> Print the minimum number of steps.

Constraints :

> 1 <= n <= 10 ^ 6 <br>
Time Limit: 1 sec

Following is Code

from sys import maxsize as MAX_VALUE 


dic = {}
def countMinStepsToOne(n) :
    if n == 1:
        return 0
    if n % 3 == 0:
        if n/3 not in dic:
            dic[n/3] = countMinStepsToOne(n/3)
    if n % 2 == 0:
        if n/2 not in dic:
            dic[n/2] = countMinStepsToOne(n/2)
    if n-1 not in dic:    
        dic[n-1] = countMinStepsToOne(n-1)
    return 1 + min(dic.get(n/3,MAX_VALUE),dic.get(n/2,MAX_VALUE),dic.get(n-1,MAX_VALUE))



#main
n = int(input())
print(countMinStepsToOne(n))

For small values of n it is giveing correct output but when I try bigger value, lets take 5685 the powershell kill the process without output and in jupyter notebook kernel goes dead.<br>
According to me I think dictionary is cause problem because when I tried to print dic it was empty, But still not getting how it worked for smaller value not bigger ones.

Doing this recursively means you're essentially doing a DFS of the possibility space, which is going to create a very deep stack (I got a RecursionError when running your code on a large input) and potentially waste a lot of time computing very long paths that you'll end up recomputing later to find a shorter route to the same value. The larger the input, the worse this effect gets.

I'd suggest doing this as a BFS instead, e.g.:

def steps_to_one(n):
    visited = set()
    depth = 0
    level = {n}
    while 1 not in level:
        depth += 1
        next_level = set()
        for n in level:
            if n in visited:
                continue
            visited.add(n)
            if n % 3 == 0:
                next_level.add(n // 3)
            if n % 2 == 0:
                next_level.add(n // 2)
            next_level.add(n - 1)
        level = next_level
    return depth

This very quickly returns the result 15 for the input 5685.

At each iteration, level is the current level of the search space, and depth is the number of levels we've traversed so far.

We keep track of visited so that if we end up at a value that we've already visited in a previous search path, we can ignore it quickly (e.g. if we go down the n - 1 path and discover a value that we were already able to get to a faster way, there's no point in re-computing the path from that point). We don't need a dict to keep track of what the depth was when we found that value, we just need to know that it's a possibility that's already in the process of being explored.

If we add a print to the bottom of the while loop:

print(depth, sorted(level - visited))

we can see what's being explored at each level of the BFS:

1000
1 [500, 999]
2 [250, 333, 499, 998]
3 [111, 125, 249, 332, 498, 997]
4 [37, 83, 110, 124, 166, 248, 331, 497, 996]
5 [36, 55, 62, 82, 109, 123, 165, 247, 330, 496, 995]
6 [12, 18, 31, 35, 41, 54, 61, 81, 108, 122, 164, 246, 329, 495, 994]
7 [4, 6, 9, 11, 17, 27, 30, 34, 40, 53, 60, 80, 107, 121, 163, 245, 328, 494, 993]
8 [2, 3, 5, 8, 10, 15, 16, 20, 26, 29, 33, 39, 52, 59, 79, 106, 120, 162, 244, 327, 493, 992]
9 [1, 7, 13, 14, 19, 25, 28, 32, 38, 51, 58, 78, 105, 119, 161, 243, 326, 492, 991]
9