What Is "Reduce a Number to 1"?
Given an integer X, find the minimum number of operations to turn X into 1 using only these three operations:
- •÷3 — divide by 3, allowed only when X is a multiple of 3.
- •÷2 — divide by 2, allowed only when X is even.
- •−1 — subtract 1 from X.
On AlgoNote, this is visualized as a story: resetting a toy shop's "magic counter" to 1 with the fewest button clicks.
Why Does Greedy Fail?
The intuition "just divide as big as possible" (greedy) is wrong here.
Take X = 10.
- •Greedy (it's even, so ÷2 first): 10 → 5 → 4 → 2 → 1 = 4 ops
- •Optimal: 10 → 9(−1) → 3(÷3) → 1(÷3) = 3 ops
Doing −1 first to reach 9 lets us apply ÷3 twice. The biggest available division is not always best — that's exactly why we need DP.
The DP Recurrence
Define dp[i] as "the minimum operations to turn i into 1".
- •Base case:
dp[1] = 0(already 1, no operation needed) - •Recurrence:
dp[i] = 1 + min(
dp[i - 1], // −1 (always available)
dp[i / 2] if i % 2 == 0, // ÷2 (only if even)
dp[i / 3] if i % 3 == 0 // ÷3 (only if multiple of 3)
)The state just before reaching i must be one of i-1, i/2, or i/3. We take the minimum of their answers and add 1 for the current operation.
How It Works
Step 1. Start with dp[1] = 0 and set the rest to ∞ (unknown).
Step 2. Fill from small to large, from 2 up to X. When computing dp[i], the values dp[i-1], dp[i/2], dp[i/3] are all already finalized.
Step 3. dp[X] is the final answer.
Time and Space Complexity
| Complexity | |
|---|---|
| Time | O(X) |
| Space | O(X) |
Each i is computed once, comparing only a constant number (at most 3) of candidates, giving O(X) overall.
Common Mistakes
- •Index 0 handling:
dp[1] = 0is the base case. Index 0 is unused. - •Missing division conditions: Add ÷2 as a candidate only when even, and ÷3 only when a multiple of 3.
- •Solving with greedy: As shown above, "divide big first" greedy has counterexamples. Always use DP to store optimal answers of all smaller numbers.
See It in Action on AlgoNote
Follow, step by step, which operation (−1 / ÷2 / ÷3) makes each cell dp[i] minimal. Change the starting number to experiment and see exactly when greedy falls into a trap.