Minimum Operations to Reach N using Primitive Calculator

Problem

You have a primitive calculator that can transform a current number x using exactly one of the operations:

1. x -> x + 1 (add 1)
2. x -> 2 * x (multiply by 2)
3. x -> 3 * x (multiply by 3)

Given a target n (n >= 1), find the minimum number of operations needed to reach n starting from 1, and output one optimal sequence of intermediate numbers (including 1 and n). If multiple optimal sequences exist, any one is acceptable.

Examples

Example 1

Input: n = 5
Output: steps = 3, path = [1, 2, 4, 5]
Explanation: 1 -> 2 (x2), 2 -> 4 (x2), 4 -> 5 (+1). Another optimal path: 1 -> 3 -> 4 -> 5.

Example 2

Input: n = 10
Output: steps = 3, path = [1, 3, 9, 10]
Explanation: 1 -> 3 (x3), 3 -> 9 (x3), 9 -> 10 (+1).

Example 3

Input: n = 96234
Output: steps = 14 (one possible path)
Path (example): [1, 3, 9, 10, 11, 22, 66, 198, 594, 1782, 5346, 16038, 16039, 32078, 96234]
Explanation: Path length is minimal; other optimal variants exist.

Solution

We want the shortest sequence of transformations from 1 to n under operations +1, *2, *3. This is equivalent to shortest path in an implicit DAG if we consider transitions forward, or a reverse greedy/bfs using operations /2, /3, -1 when valid. A dynamic programming approach is straightforward and reconstructs the path.

Method 1 - Naive Recursion - Count Only

Intuition

Directly encode the recurrence:

f(1) = 0
f(n) = 1 + min( f(n-1), f(n/2) if n%2==0, f(n/3) if n%3==0 )

This explores all possible derivation trees. It recomputes overlapping subproblems many times → exponential time. It is useful only to illustrate the optimal substructure before introducing memoization / DP.

Notes

• Extremely slow beyond small n (e.g., > 10^3 already impractical).
• We usually compute ONLY the count here; constructing the full path naively would require returning and copying vectors at each step (further overhead).

Pseudocode

def naive(n):
    if n == 1: return 0
    best = naive(n-1)
    if n % 2 == 0:
        best = min(best, naive(n//2))
    if n % 3 == 0:
        best = min(best, naive(n//3))
    return best + 1

Code

C++

int naiveCount(int n) {
    if (n <= 1) return 0;
    int best = naiveCount(n-1);
    if (n % 2 == 0) best = min(best, naiveCount(n/2));
    if (n % 3 == 0) best = min(best, naiveCount(n/3));
    return best + 1;
}

Go

func naiveCount(n int) int {
    if n <= 1 { return 0 }
    best := naiveCount(n-1)
    if n%2 == 0 { if v := naiveCount(n/2); v < best { best = v } }
    if n%3 == 0 { if v := naiveCount(n/3); v < best { best = v } }
    return best + 1
}

Java

int naiveCount(int n) {
    if (n <= 1) return 0;
    int best = naiveCount(n - 1);
    if (n % 2 == 0) best = Math.min(best, naiveCount(n / 2));
    if (n % 3 == 0) best = Math.min(best, naiveCount(n / 3));
    return best + 1;
}

Python

def naive_count(n: int) -> int:
    if n <= 1:
        return 0
    best = naive_count(n - 1)
    if n % 2 == 0:
        best = min(best, naive_count(n // 2))
    if n % 3 == 0:
        best = min(best, naive_count(n // 3))
    return best + 1

Complexity

• Time: Exponential (roughly O(3^{log n}) in worst reasoning; practically explosive).
• Space: O(n) recursion depth in worst case (chain of -1 operations).

Method 2 - Top-Down Memoized Recursion (Path Reconstruction)

Intuition

Add a cache to the naive recurrence. Each f(k) is computed once, giving O(n) states and O(1) transitions each (just up to three candidates). We also record the predecessor that achieved the minimum so we can rebuild the path – mirroring the logic of bottom-up DP but in a depth-first way.

Approach

1. Allocate arrays dp[0..n] initialized to -1 and parent[0..n].
2. Recursive function solve(x):
   • If x == 1, return 0.
   • If dp[x] != -1, return cached.
   • Try candidates from x-1, x/2 (if divisible), x/3 (if divisible); pick best.
   • Store dp[x] = best + 1 and parent[x] = predecessor.
3. After solve(n), reconstruct path by following parent from n to 1 then reversing.

Pseudocode

dp = [-1]*(n+1)
parent = [0]*(n+1)

def solve(x):
    if x == 1: return 0
    if dp[x] != -1: return dp[x]
    best_val = solve(x-1)
    best_prev = x-1
    if x % 2 == 0:
        v = solve(x//2)
        if v < best_val:
            best_val, best_prev = v, x//2
    if x % 3 == 0:
        v = solve(x//3)
        if v < best_val:
            best_val, best_prev = v, x//3
    dp[x] = best_val + 1
    parent[x] = best_prev
    return dp[x]

solve(n)
path = []
cur = n
while cur >= 1:
    path.append(cur)
    if cur == 1: break
    cur = parent[cur]
path.reverse()

Code

C++

#include <vector>
using namespace std;

class SolutionTopDown {
    vector<int> dp, parent;
    int solve(int x) {
        if (x == 1) return 0;
        if (dp[x] != -1) return dp[x];
        int bestVal = solve(x - 1);
        int bestPrev = x - 1;
        if (x % 2 == 0) {
            int v = solve(x / 2);
            if (v < bestVal) { bestVal = v; bestPrev = x / 2; }
        }
        if (x % 3 == 0) {
            int v = solve(x / 3);
            if (v < bestVal) { bestVal = v; bestPrev = x / 3; }
        }
        parent[x] = bestPrev;
        return dp[x] = bestVal + 1;
    }
public:
    vector<int> minOperationsPath(int n) {
        if (n <= 1) return {1};
        dp.assign(n + 1, -1);
        parent.assign(n + 1, 0);
        solve(n);
        vector<int> path;
        for (int cur = n; cur >= 1; cur = parent[cur]) path.push_back(cur);
        reverse(path.begin(), path.end());
        return path;
    }
};

Go

package main

type topDownSolver struct {
    dp     []int
    parent []int
}

func (s *topDownSolver) solve(x int) int {
    if x == 1 { return 0 }
    if s.dp[x] != -1 { return s.dp[x] }
    bestVal := s.solve(x-1)
    bestPrev := x - 1
    if x%2 == 0 {
        v := s.solve(x/2)
        if v < bestVal { bestVal = v; bestPrev = x/2 }
    }
    if x%3 == 0 {
        v := s.solve(x/3)
        if v < bestVal { bestVal = v; bestPrev = x/3 }
    }
    s.parent[x] = bestPrev
    s.dp[x] = bestVal + 1
    return s.dp[x]
}

func minOperationsPathTopDown(n int) []int {
    if n <= 1 { return []int{1} }
    s := &topDownSolver{dp: make([]int, n+1), parent: make([]int, n+1)}
    for i := 0; i <= n; i++ { s.dp[i] = -1 }
    s.solve(n)
    path := []int{}
    for cur := n; cur >= 1; cur = s.parent[cur] { path = append(path, cur) }
    // reverse
    for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 { path[i], path[j] = path[j], path[i] }
    return path
}

Java

import java.util.*;

class SolutionTopDown {
    int[] dp;
    int[] parent;
    int solve(int x) {
        if (x == 1) return 0;
        if (dp[x] != -1) return dp[x];
        int bestVal = solve(x - 1);
        int bestPrev = x - 1;
        if (x % 2 == 0) {
            int v = solve(x / 2);
            if (v < bestVal) { bestVal = v; bestPrev = x / 2; }
        }
        if (x % 3 == 0) {
            int v = solve(x / 3);
            if (v < bestVal) { bestVal = v; bestPrev = x / 3; }
        }
        parent[x] = bestPrev;
        return dp[x] = bestVal + 1;
    }
    public List<Integer> minOperationsPath(int n) {
        if (n <= 1) return Arrays.asList(1);
        dp = new int[n + 1];
        parent = new int[n + 1];
        Arrays.fill(dp, -1);
        solve(n);
        List<Integer> path = new ArrayList<>();
        for (int cur = n; cur >= 1; cur = parent[cur]) path.add(cur);
        Collections.reverse(path);
        return path;
    }
}

Python

from functools import lru_cache
from typing import List

class SolutionTopDown:
    def minOperationsPath(self, n: int) -> List[int]:
        if n <= 1:
            return [1]
        parent = [0]*(n+1)
        @lru_cache(None)
        def solve(x: int) -> int:
            if x == 1:
                return 0
            best_val = solve(x-1)
            best_prev = x-1
            if x % 2 == 0:
                v = solve(x//2)
                if v < best_val:
                    best_val, best_prev = v, x//2
            if x % 3 == 0:
                v = solve(x//3)
                if v < best_val:
                    best_val, best_prev = v, x//3
            parent[x] = best_prev
            return best_val + 1
        solve(n)
        path: List[int] = []
        cur = n
        while cur >= 1:
            path.append(cur)
            if cur == 1:
                break
            cur = parent[cur]
        path.reverse()
        return path

Complexity

• Time: O(n) states, each examines up to 3 predecessors → O(n).
• Space: O(n) for memo + O(n) recursion stack worst case (chain of -1 transitions).

Method 3 - Bottom-up Dynamic Programming (Path Reconstruction)

Intuition

• Define dp[i] as the minimum number of operations to reach i from 1.
• Every number i can be reached from: i-1, i/2 if i divisible by 2, and i/3 if divisible by 3.
• Therefore the optimal cost for i is 1 + min(dp[i-1], dp[i/2] if divisible, dp[i/3] if divisible).
• Storing the predecessor that yielded the minimum lets us rebuild the optimal path from n back to 1.

Approach

1. Initialize arrays dp[0..n] with large values; set dp[1] = 0 (zero operations to reach 1).
2. For each i from 2 to n:
   • Start with candidate = dp[i-1] (via +1).
   • If i % 2 == 0, candidate = min(candidate, dp[i/2]).
   • If i % 3 == 0, candidate = min(candidate, dp[i/3]).
   • Set dp[i] = candidate + 1 and record which predecessor produced the min.
3. Reconstruct path: starting at n, repeatedly push it into a list and jump to recorded predecessor until reaching 1; then reverse.
4. Return dp[n] (operations count) and the path list.

Edge cases:

• n = 1 -> steps = 0, path = [1].
• Large n up to typical constraints (e.g., 1e6) fits in memory/time due to O(n).

Code

All implementations expose a function named minOperationsPath returning the sequence (including 1 and n). The number of operations is len(path) - 1.

C++

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> minOperationsPath(int n) {
        if (n <= 1) return {1};
        vector<int> dp(n + 1, 0), parent(n + 1, -1);
        dp[1] = 0; parent[1] = 0;
        for (int i = 2; i <= n; ++i) {
            int bestPrev = i - 1;
            int bestVal = dp[i - 1];
            if (i % 2 == 0 && dp[i / 2] < bestVal) {
                bestVal = dp[i / 2];
                bestPrev = i / 2;
            }
            if (i % 3 == 0 && dp[i / 3] < bestVal) {
                bestVal = dp[i / 3];
                bestPrev = i / 3;
            }
            dp[i] = bestVal + 1;
            parent[i] = bestPrev;
        }
        vector<int> path;
        for (int cur = n; cur >= 1; cur = parent[cur]) path.push_back(cur);
        reverse(path.begin(), path.end());
        return path;
    }
};

Go

package main

func minOperationsPath(n int) []int {
    if n <= 1 { return []int{1} }
    dp := make([]int, n+1)
    parent := make([]int, n+1)
    parent[1] = 0
    for i := 2; i <= n; i++ {
        bestPrev := i - 1
        bestVal := dp[i-1]
        if i%2 == 0 && dp[i/2] < bestVal {
            bestVal = dp[i/2]
            bestPrev = i / 2
        }
        if i%3 == 0 && dp[i/3] < bestVal {
            bestVal = dp[i/3]
            bestPrev = i / 3
        }
        dp[i] = bestVal + 1
        parent[i] = bestPrev
    }
    path := []int{}
    for cur := n; cur >= 1; cur = parent[cur] {
        path = append(path, cur)
    }
    // reverse
    for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 { path[i], path[j] = path[j], path[i] }
    return path
}

Java

import java.util.*;

class Solution {
    public List<Integer> minOperationsPath(int n) {
        if (n <= 1) return Arrays.asList(1);
        int[] dp = new int[n + 1];
        int[] parent = new int[n + 1];
        parent[1] = 0;
        for (int i = 2; i <= n; i++) {
            int bestPrev = i - 1;
            int bestVal = dp[i - 1];
            if (i % 2 == 0 && dp[i / 2] < bestVal) { bestVal = dp[i / 2]; bestPrev = i / 2; }
            if (i % 3 == 0 && dp[i / 3] < bestVal) { bestVal = dp[i / 3]; bestPrev = i / 3; }
            dp[i] = bestVal + 1;
            parent[i] = bestPrev;
        }
        List<Integer> path = new ArrayList<>();
        for (int cur = n; cur >= 1; cur = parent[cur]) path.add(cur);
        Collections.reverse(path);
        return path;
    }
}

Python

from typing import List

class Solution:
    def minOperationsPath(self, n: int) -> List[int]:
        if n <= 1:
            return [1]
        dp = [0] * (n + 1)
        parent = [0] * (n + 1)
        for i in range(2, n + 1):
            best_prev = i - 1
            best_val = dp[i - 1]
            if i % 2 == 0 and dp[i // 2] < best_val:
                best_val = dp[i // 2]
                best_prev = i // 2
            if i % 3 == 0 and dp[i // 3] < best_val:
                best_val = dp[i // 3]
                best_prev = i // 3
            dp[i] = best_val + 1
            parent[i] = best_prev
        path: List[int] = []
        cur = n
        while cur >= 1:
            path.append(cur)
            cur = parent[cur]
        path.reverse()
        return path

Complexity

• ⏰ Time complexity: O(n) — each value from 2..n computed in O(1) combining up to three previous states.
• 🧺 Space complexity: O(n) — arrays dp and parent of length n+1.

Method 4 - Reverse BFS

Intuition

• Starting from n, we can move backwards using inverse operations: if x divisible by 3 go to x/3, if divisible by 2 go to x/2, always can go to x-1.
• This forms an unweighted graph; BFS finds the shortest path length. However, worst-case exploring many numbers near n makes this comparable or worse than linear DP. Included for conceptual symmetry.

Approach

1. BFS queue seeded with n; store predecessor map.
2. At each pop x, generate neighbors: x/3 (if divisible), x/2 (if divisible), x-1.
3. Stop when reaching 1 and reconstruct path by following predecessors forward (then reverse for 1..n or reverse BFS order accordingly).
4. This avoids building arrays up to n if early termination beneficial (not typical here since we usually must consider most numbers anyway).

Code

Python

from collections import deque
from typing import List

class SolutionBFS:
    def minOperationsPath(self, n: int) -> List[int]:
        if n <= 1:
            return [1]
        q = deque([n])
        parent = {n: None}
        while q:
            x = q.popleft()
            if x == 1:
                break
            if x % 3 == 0 and x // 3 not in parent:
                parent[x // 3] = x
                q.append(x // 3)
            if x % 2 == 0 and x // 2 not in parent:
                parent[x // 2] = x
                q.append(x // 2)
            if x - 1 not in parent:
                parent[x - 1] = x
                q.append(x - 1)
        path = []
        cur = 1
        while cur is not None:
            path.append(cur)
            cur = parent[cur]
        path.reverse()  # now 1..n
        return path

Complexity

• ⏰ Time complexity: O(n) worst-case — each integer from 1..n may be enqueued at most once.
• 🧺 Space complexity: O(n) — parent map / queue.