Problem statement

https://binarysearch.com/problems/Number-of-Decrements-to-Reach-Zero/

Solution

Actually here we can use usual bfs or dp. Why it will work, because we can show that we have no more thant O(log n) different numbers on each level. First level is n//2, n//3 and around, then it is n//2//2, n//2//3, n//3, n//3 and so on.

Complexity

It is O(log^2 n) for time and O(log n) for space.

Code

class Solution:
    def solve(self, n):
        if n == 0: return 0
        Q = deque([(0, n)])
        V = set([n])
        while Q:
            steps, x = Q.popleft()
            if x == 0: return steps
            cands = [x - 1]
            if x % 3 == 0: cands += [x//3]
            if x % 2 == 0: cands += [x//2]
            for cand in cands:
                if cand not in V:
                    Q.append((steps + 1, cand))
                    V.add(cand)