14.31 Minimum Operations to One

14.31.1 Problem Metadata

• Platform: Interview
• Problem ID: NA
• Difficulty: Medium
• URL: N/A
• Tags:
• Techniques: Recursion, Dynamic Programming, Memoization

14.31.2 Description

Given an integer n, you may perform operations: n = n - 1, n = n / 2 (if even), or n = n / 3 (if divisible by 3). Return the minimum number of operations needed to reduce n to 1.

14.31.3 Examples

Input: 9
Output: 2  // 9 -> 3 -> 1

Input: 8
Output: 3  // 8 -> 4 -> 2 -> 1

14.31.4 Constraints

• 1 <= n <= 10^6

14.31.5 Solution - Memoized Recursion

14.31.5.1 Walkthrough

Define dp[n] as the minimal operations to reach 1. Recursively compute each option and cache results to avoid recomputation.

14.31.5.2 Analysis

• Time Complexity: O(n)
• Space Complexity: O(n) for memoization

14.31.5.3 Implementation Steps

1. Base case: dp[1] = 0.
2. For other n, evaluate 1 + dp[n-1].
3. If divisible by 2 or 3, also consider 1 + dp[n/2], 1 + dp[n/3].
4. Store the minimum in memo.

14.31.5.4 Code - Java

public int minStepsToOne(int n) {
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    return dfs(n, memo);
}

private int dfs(int n, int[] memo) {
    if (n == 1) {
        return 0;
    }
    if (memo[n] != -1) {
        return memo[n];
    }
    int best = 1 + dfs(n - 1, memo);
    if (n % 2 == 0) {
        best = Math.min(best, 1 + dfs(n / 2, memo));
    }
    if (n % 3 == 0) {
        best = Math.min(best, 1 + dfs(n / 3, memo));
    }
    return memo[n] = best;
}