232. 2 Keys Keyboard
🔗 LeetCode Problem: 650. 2 Keys Keyboard
📊 Difficulty: Medium
🏷️ Topics: Dynamic Programming, Math, Prime Factorization
Problem Statement
There is only one character 'A' on the screen of a notepad. You can perform one of two operations on this notepad for each step:
- Copy All: You can copy all the characters present on the screen (a partial copy is not allowed).
- Paste: You can paste the characters which are copied last time.
Given an integer n, return the minimum number of operations to get the character 'A' exactly n times on the screen.
Example 1:
Input: n = 3
Output: 3
Explanation: Initially, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.
Example 2:
Input: n = 1
Output: 0
Explanation: We already have 'A' on screen.
Constraints:
- 1 <= n <= 1000
🌳 Visual Understanding - Building Intuition from Scratch
The Problem We're Solving:
Start: A (1 character on screen)
Goal: Get exactly n A's on screen
Available operations:
1. Copy All - copies everything currently on screen to clipboard
2. Paste - pastes clipboard content to screen
Question: Minimum operations to reach n A's? 🤔
Let's Understand by Building Small Examples:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
n = 1: Already have A
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Operations: 0
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
n = 2: Need AA
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Start: A
Copy: clipboard = A (1 op)
Paste: screen = AA (1 op)
Total: 2 operations
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
n = 3: Need AAA
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Start: A
Copy: clipboard = A (1 op)
Paste: screen = AA (1 op)
Paste: screen = AAA (1 op)
Total: 3 operations
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
n = 4: Need AAAA
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Option 1: From 1 → 4 directly
Copy(1), Paste, Paste, Paste
Operations: 1 + 3 = 4
Option 2: From 1 → 2 → 4
1 → 2: Copy(1), Paste = 2 ops
2 → 4: Copy(2), Paste = 2 ops
Total: 2 + 2 = 4 operations
Both same! But notice: 4 = 2 × 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
n = 6: Need AAAAAA
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Option 1: From 1 → 6 directly
Copy(1), Paste × 5
Operations: 1 + 5 = 6
Option 2: From 1 → 2 → 6
1 → 2: Copy(1), Paste = 2 ops
2 → 6: Copy(2), Paste × 2 = 3 ops
Total: 2 + 3 = 5 operations ✓
Option 3: From 1 → 3 → 6
1 → 3: Copy(1), Paste × 2 = 3 ops
3 → 6: Copy(3), Paste = 2 ops
Total: 3 + 2 = 5 operations ✓
Best: 5 operations
Notice: 6 = 2 × 3, operations = 2 + 3 = 5!
The Pattern Emerging:
KEY OBSERVATION:
To go from i to j (where j is multiple of i):
- Copy once: 1 operation
- Paste (j/i - 1) times: (j/i - 1) operations
- Total: 1 + (j/i - 1) = j/i operations
Examples:
1 → 2: 2/1 = 2 operations (copy, paste)
2 → 6: 6/2 = 3 operations (copy, paste, paste)
3 → 6: 6/3 = 2 operations (copy, paste)
CRITICAL INSIGHT:
If n = a × b:
We can go 1 → a → n
Cost = (ops to get a) + b
Example: n = 6 = 2 × 3
1 → 2: 2 ops
2 → 6: 3 ops
Total: 2 + 3 = 5 ops ✓
🧠 The AHA Moment - Recursive Thinking
The Fundamental Question:
To get n A's, where can we come from?
Answer: We must come from some divisor d of n!
Why? Because:
- We can only multiply what we have (via copy-paste)
- If we have d A's and copy-paste, we get multiples of d
- To reach n, we need n to be a multiple of d
- So d must be a DIVISOR of n
Example: n = 6
Can come from: 1, 2, or 3 (divisors of 6)
Cannot come from: 4 or 5 (not divisors)
Building the Recursive Intuition:
Think recursively:
To get n A's:
1. First, get d A's (where d divides n)
2. Then multiply d to get n (by copy-paste)
Cost:
- Cost to get d A's: minSteps(d)
- Cost to multiply d by (n/d): n/d operations
(1 copy + (n/d - 1) pastes = n/d total)
Total: minSteps(d) + n/d
Try all divisors d, take minimum!
Base case: n = 1 → 0 operations (already have it)
Concrete Example - n = 12:
12 can be built from its divisors:
Option 1: From 1
minSteps(1) + 12 = 0 + 12 = 12 ops
Option 2: From 2
minSteps(2) + 6 = 2 + 6 = 8 ops
Option 3: From 3
minSteps(3) + 4 = 3 + 4 = 7 ops ✓
Option 4: From 4
minSteps(4) + 3 = 4 + 3 = 7 ops ✓
Option 5: From 6
minSteps(6) + 2 = 5 + 2 = 7 ops ✓
Minimum: 7 operations
Notice: 12 = 2 × 2 × 3 (prime factorization)
Operations = 2 + 2 + 3 = 7 ✓
The pattern: Sum of prime factors!
🔴 Approach 1: Recursion (Top-Down Thinking)
📐 Function Definition
Function Signature:
int minSteps(int n)
What does this function compute?
- Input n: Target number of A's on screen
- Output: Minimum operations needed to get exactly n A's starting from 1 A
What does the recursive call mean?
- minSteps(d) = Minimum operations to get d A's from 1 A
- We use this to build n A's from d A's
The Recursive Formula:
minSteps(n) = minimum of:
{
minSteps(d) + n/d for all divisors d of n (where d < n)
}
Base case:
minSteps(1) = 0 (already have 1 A)
Why this recurrence works:
To get n A's, we must come from some divisor d:
Step 1: Get d A's → costs minSteps(d) operations
Step 2: Copy d A's → costs 1 operation
Step 3: Paste (n/d - 1) times → costs (n/d - 1) operations
Total for step 2 & 3: 1 + (n/d - 1) = n/d operations
Overall cost: minSteps(d) + n/d
We try all divisors d of n and pick the minimum!
💡 Intuition - The Recursive Thought Process
Think of it like building blocks:
To build n = 12:
I could build 12 from 1:
┌─────────────┐
│ 1 → → → 12 │ Cost: minSteps(1) + 12 = 0 + 12 = 12 ops
└─────────────┘
Or build 12 from 2:
┌─────┐ ┌──────┐
│ 1→2 │ │ 2→12 │ Cost: minSteps(2) + 6
└─────┘ └──────┘ = 2 + 6 = 8 ops
Or build 12 from 3:
┌─────┐ ┌──────┐
│ 1→3 │ │ 3→12 │ Cost: minSteps(3) + 4
└─────┘ └──────┘ = 3 + 4 = 7 ops ✓
Or build 12 from 4:
┌─────┐ ┌──────┐
│ 1→4 │ │ 4→12 │ Cost: minSteps(4) + 3
└─────┘ └──────┘ = 4 + 3 = 7 ops ✓
Or build 12 from 6:
┌─────┐ ┌──────┐
│ 1→6 │ │ 6→12 │ Cost: minSteps(6) + 2
└─────┘ └──────┘ = 5 + 2 = 7 ops ✓
I pick the minimum: 7 operations!
The recursive structure naturally tries all valid paths!
📝 Implementation - Pure Recursion
class Solution {
public int minSteps(int n) {
// Base case: already have 1 A
if (n == 1) return 0;
int minOps = n; // Worst case: copy from 1, paste (n-1) times
// Try all divisors d of n (where d < n)
for (int d = 2; d < n; d++) {
if (n % d == 0) {
// n is divisible by d
// Cost: get d A's, then multiply by (n/d)
int cost = minSteps(d) + n / d;
minOps = Math.min(minOps, cost);
}
}
return minOps;
}
}
🔍 Detailed Dry Run: n = 6
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
CALL: minSteps(6)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
n = 6, not base case
minOps = 6 (worst case: from 1)
Check divisors of 6:
d = 2: 6 % 2 = 0 ✓
┌─────────────────────────────────┐
│ CALL: minSteps(2) │
│ ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━│
│ n = 2, not base case │
│ minOps = 2 │
│ │
│ Check divisors of 2: │
│ (no divisor d where 2 ≤ d < 2)│
│ │
│ RETURN: 2 │
└─────────────────────────────────┘
cost = minSteps(2) + 6/2
= 2 + 3
= 5 ✓
minOps = min(6, 5) = 5
d = 3: 6 % 3 = 0 ✓
┌─────────────────────────────────┐
│ CALL: minSteps(3) │
│ ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━│
│ n = 3, not base case │
│ minOps = 3 │
│ │
│ Check divisors of 3: │
│ d = 2: 3 % 2 ≠ 0 │
│ (no valid divisor) │
│ │
│ RETURN: 3 │
└─────────────────────────────────┘
cost = minSteps(3) + 6/3
= 3 + 2
= 5 ✓
minOps = min(5, 5) = 5
d = 4: 6 % 4 ≠ 0, skip
d = 5: 6 % 5 ≠ 0, skip
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RETURN: 5 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Explanation of result:
6 = 2 × 3 or 6 = 3 × 2
Path 1: 1 → 2 → 6
1 → 2: minSteps(2) = 2 operations
2 → 6: 3 operations (copy, paste, paste)
Total: 2 + 3 = 5 operations ✓
Path 2: 1 → 3 → 6
1 → 3: minSteps(3) = 3 operations
3 → 6: 2 operations (copy, paste)
Total: 3 + 2 = 5 operations ✓
Both paths give the same answer!
Why This Is Slow:
Overlapping subproblems!
Example: To compute minSteps(12):
Calls minSteps(2), minSteps(3), minSteps(4), minSteps(6)
Later, if we compute minSteps(18):
Calls minSteps(2) ← repeated!
Calls minSteps(3) ← repeated!
Calls minSteps(6) ← repeated!
Calls minSteps(9)
Same subproblems computed multiple times!
Solution: Use memoization or DP! 💡
📊 Complexity Analysis
Time Complexity: O(n² √n) without memoization
For each number from 1 to n:
Check divisors: O(√n) on average
But with recursion overlap: could be worse
Very slow for large n!
Space Complexity: O(n)
Recursion stack depth up to n
Why We Need Optimization:
❌ Repeats same calculations
❌ For n = 1000, too slow
✅ But shows the recursive structure clearly!
Next: Add memoization or bottom-up DP!
🟡 Approach 2: Memoization (Top-Down DP)
📐 Function Definition
Function Signature:
int minSteps(int n)
What it represents:
Variables we track:
- memo[i] = Minimum operations to get i A's from 1 A
- If computed, reuse it!
- If not computed, compute and cache it!
Purpose: - Same recursive logic as Approach 1 - But CACHE results to avoid recomputation - Each state solved only ONCE!
Key Understanding:
Without memo: minSteps(6) computed multiple times
With memo: minSteps(6) computed ONCE, cached!
First call to minSteps(6):
- Compute the answer
- Store in memo[6]
Next call to minSteps(6):
- Check memo[6]
- Found! Return immediately
- No recomputation! ✓
💡 Intuition
The smart idea: Remember what we've already computed!
Think of it like a lookup table:
WITHOUT memoization:
Question: "Min ops to get 6 A's?"
You: *compute recursively*
Later, same question again!
You: *compute recursively AGAIN* ❌
WITH memoization:
Question: "Min ops to get 6 A's?"
You: *compute recursively*
You: *write in table: memo[6] = 5*
Later, same question again!
You: *check table memo[6]*
You: "It's 5!" ✓
You: *instant answer!*
The memo array is our lookup table!
📝 Implementation
class Solution {
private int[] memo;
public int minSteps(int n) {
memo = new int[n + 1];
Arrays.fill(memo, -1); // -1 means not computed
return helper(n);
}
private int helper(int n) {
// Base case
if (n == 1) return 0;
// Check memo
if (memo[n] != -1) {
return memo[n];
}
int minOps = n; // Worst case
// Try all divisors
for (int d = 2; d < n; d++) {
if (n % d == 0) {
int cost = helper(d) + n / d;
minOps = Math.min(minOps, cost);
}
}
// Save to memo
memo[n] = minOps;
return minOps;
}
}
🔍 Detailed Dry Run: n = 12
memo = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
0 1 2 3 4 5 6 7 8 9 10 11 12
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
CALL: helper(12)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
memo[12] = -1 (not computed)
minOps = 12
d = 2: 12 % 2 = 0 ✓
helper(2):
memo[2] = -1 (not computed)
minOps = 2 (no smaller divisors)
memo[2] = 2 ✓
return 2
cost = 2 + 6 = 8
minOps = min(12, 8) = 8
d = 3: 12 % 3 = 0 ✓
helper(3):
memo[3] = -1 (not computed)
minOps = 3 (no valid divisors)
memo[3] = 3 ✓
return 3
cost = 3 + 4 = 7
minOps = min(8, 7) = 7
d = 4: 12 % 4 = 0 ✓
helper(4):
memo[4] = -1 (not computed)
Check d = 2: 4 % 2 = 0
helper(2): memo[2] = 2 ← cached! ✓
cost = 2 + 2 = 4
memo[4] = 4 ✓
return 4
cost = 4 + 3 = 7
minOps = min(7, 7) = 7
d = 5: 12 % 5 ≠ 0, skip
d = 6: 12 % 6 = 0 ✓
helper(6):
memo[6] = -1 (not computed)
Check d = 2: helper(2) = 2 ← cached! ✓
cost = 2 + 3 = 5
Check d = 3: helper(3) = 3 ← cached! ✓
cost = 3 + 2 = 5
memo[6] = 5 ✓
return 5
cost = 5 + 2 = 7
minOps = min(7, 7) = 7
memo[12] = 7 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL memo state:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
memo = [-1, 0, 2, 3, 4, -1, 5, -1, -1, -1, -1, -1, 7]
0 1 2 3 4 5 6 7 8 9 10 11 12
Each value computed ONCE and cached! ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 7 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
12 = 2 × 2 × 3 (prime factorization)
Operations = 2 + 2 + 3 = 7 ✓
Why This Works:
KEY INSIGHT:
Each unique n is solved ONCE
Result is cached in memo[n]
Future calls return cached result instantly
Comparison:
Pure recursion: helper(2) called many times
Memoization: helper(2) computed ONCE, cached
This transforms exponential → polynomial time!
📊 Complexity Analysis
Time Complexity: O(n × √n)
n = target number
States: n different values (1 to n)
For each state: check divisors O(√n)
Total: O(n × √n)
For n = 1000:
1000 × 32 ≈ 32,000 operations
Much better! ✓
Space Complexity: O(n)
Memo array: O(n)
Recursion stack: O(n) worst case
Total: O(n)
🟢 Approach 3: Bottom-Up DP (Iterative)
📐 Function Definition
Function Signature:
int minSteps(int n)
What it represents:
DP Array:
- dp[i] = Minimum operations to get i A's from 1 A
- Build from dp[1], dp[2], ..., up to dp[n]
- Use smaller values to compute larger values!
Purpose: - No recursion, build iteratively - For each i, try all divisors j - dp[i] = min(dp[j] + i/j) for all j dividing i
Key Understanding:
Bottom-up builds from smallest to largest:
dp[1] = 0 (base case)
dp[2] = dp[1] + 2 = 0 + 2 = 2
dp[3] = dp[1] + 3 = 0 + 3 = 3
dp[4] = min(dp[1] + 4, dp[2] + 2) = min(4, 4) = 4
dp[6] = min(dp[1] + 6, dp[2] + 3, dp[3] + 2) = min(6, 5, 5) = 5
Each value uses previously computed values!
💡 Intuition
The systematic idea: Build table from bottom up!
Think of it like filling a table:
dp[1] = 0 ✓ (already have it)
dp[2]:
From 1: 0 + 2 = 2 ✓
Result: 2
dp[3]:
From 1: 0 + 3 = 3 ✓
Result: 3
dp[4]:
From 1: 0 + 4 = 4
From 2: dp[2] + 2 = 2 + 2 = 4
Result: min(4, 4) = 4 ✓
dp[6]:
From 1: 0 + 6 = 6
From 2: dp[2] + 3 = 2 + 3 = 5 ✓
From 3: dp[3] + 2 = 3 + 2 = 5 ✓
Result: min(6, 5, 5) = 5 ✓
Build incrementally! No recursion needed!
📝 Implementation
class Solution {
public int minSteps(int n) {
if (n == 1) return 0;
// dp[i] = min operations to get i A's
int[] dp = new int[n + 1];
// Base case
dp[1] = 0;
// Build from 2 to n
for (int i = 2; i <= n; i++) {
// Start with worst case: from 1
dp[i] = i;
// Try all divisors j of i
for (int j = 2; j < i; j++) {
if (i % j == 0) {
// Can reach i from j
dp[i] = Math.min(dp[i], dp[j] + i / j);
}
}
}
return dp[n];
}
}
🔍 Detailed Dry Run: n = 12
Initial state:
dp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
- 1 2 3 4 5 6 7 8 9 10 11 12
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
BUILD DP TABLE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i = 2:
━━━━━━━━━━━━━━━━━━━━
dp[2] = 2 (default: from 1)
Check divisors: (none < 2)
dp[2] = 2 ✓
i = 3:
━━━━━━━━━━━━━━━━━━━━
dp[3] = 3 (default: from 1)
Check j = 2: 3 % 2 ≠ 0
dp[3] = 3 ✓
i = 4:
━━━━━━━━━━━━━━━━━━━━
dp[4] = 4 (default: from 1)
Check j = 2: 4 % 2 = 0 ✓
dp[4] = min(4, dp[2] + 4/2)
= min(4, 2 + 2)
= min(4, 4)
= 4
Check j = 3: 4 % 3 ≠ 0
dp[4] = 4 ✓
i = 5:
━━━━━━━━━━━━━━━━━━━━
dp[5] = 5 (default: from 1)
Check j = 2,3,4: none divide 5
dp[5] = 5 ✓
i = 6:
━━━━━━━━━━━━━━━━━━━━
dp[6] = 6 (default: from 1)
Check j = 2: 6 % 2 = 0 ✓
dp[6] = min(6, dp[2] + 6/2)
= min(6, 2 + 3)
= min(6, 5)
= 5 ✓
Check j = 3: 6 % 3 = 0 ✓
dp[6] = min(5, dp[3] + 6/3)
= min(5, 3 + 2)
= min(5, 5)
= 5
Check j = 4,5: don't divide 6
dp[6] = 5 ✓
i = 7: dp[7] = 7 (prime)
i = 8: dp[8] = min(dp[2]+4, dp[4]+2) = min(6,6) = 6
i = 9: dp[9] = min(dp[3]+3) = 6
i = 10: dp[10] = min(dp[2]+5, dp[5]+2) = min(7,7) = 7
i = 11: dp[11] = 11 (prime)
i = 12:
━━━━━━━━━━━━━━━━━━━━
dp[12] = 12 (default: from 1)
Check j = 2: 12 % 2 = 0 ✓
dp[12] = min(12, dp[2] + 6)
= min(12, 2 + 6)
= min(12, 8)
= 8
Check j = 3: 12 % 3 = 0 ✓
dp[12] = min(8, dp[3] + 4)
= min(8, 3 + 4)
= min(8, 7)
= 7 ✓
Check j = 4: 12 % 4 = 0 ✓
dp[12] = min(7, dp[4] + 3)
= min(7, 4 + 3)
= min(7, 7)
= 7
Check j = 6: 12 % 6 = 0 ✓
dp[12] = min(7, dp[6] + 2)
= min(7, 5 + 2)
= min(7, 7)
= 7
dp[12] = 7 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL DP TABLE:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp = [0, 0, 2, 3, 4, 5, 5, 7, 6, 6, 7, 11, 7]
- 1 2 3 4 5 6 7 8 9 10 11 12
Answer: dp[12] = 7 ✓
Verification:
12 = 2 × 2 × 3 (prime factorization)
Operations = 2 + 2 + 3 = 7 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 7 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Why This Works:
KEY INSIGHT:
When computing dp[i], all smaller values dp[j] (j < i)
are already computed!
We can use them directly without recursion!
This is the essence of bottom-up DP! 🎯
📊 Complexity Analysis
Time Complexity: O(n × √n)
n = target number
Outer loop: n iterations
Inner loop: check divisors, O(√n) average
Total: O(n × √n)
For n = 1000:
1000 × 32 ≈ 32,000 operations
Efficient! ✓
Space Complexity: O(n)
DP array of size n + 1
No recursion stack!
🟣 Approach 4: Prime Factorization (Mathematical)
📐 Function Definition
Function Signature:
int minSteps(int n)
What it represents:
Mathematical Approach: - Find prime factorization of n - Sum all prime factors (with repetition) - This is the minimum operations!
Purpose: - No DP needed, pure math! - Directly compute from prime factors - Elegant and optimal!
Key Understanding:
n = p₁ × p₂ × p₃ × ... (prime factorization)
Minimum operations = p₁ + p₂ + p₃ + ...
Why?
To build n optimally, multiply by primes:
1 → p₁ → p₁×p₂ → p₁×p₂×p₃ → ... → n
Each multiplication by prime p costs p operations
Total = sum of all prime factors! 🎯
💡 Intuition
The brilliant idea: It's all about prime factors!
Mathematical observation:
To build n = 12 = 2 × 2 × 3:
Optimal path:
1 → 2 (cost: 2 ops - copy, paste)
2 → 4 (cost: 2 ops - copy, paste)
4 → 12 (cost: 3 ops - copy, paste, paste)
Total: 2 + 2 + 3 = 7 ops
This equals the sum of prime factors! 🔑
Why is this optimal?
- Any other factorization uses same primes
- 12 = 3 × 4 = 3 × 2 × 2 → same primes, same sum!
- 12 = 6 × 2 = 3 × 2 × 2 → same primes, same sum!
Breaking to primes is always optimal!
📝 Implementation
class Solution {
public int minSteps(int n) {
if (n == 1) return 0;
int operations = 0;
// Find all prime factors and sum them
for (int factor = 2; factor <= n; factor++) {
while (n % factor == 0) {
operations += factor;
n /= factor;
}
}
return operations;
}
}
🔍 Detailed Dry Run: n = 12
n = 12
operations = 0
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FIND PRIME FACTORS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
factor = 2:
━━━━━━━━━━━━━━━━━━━━
12 % 2 = 0? YES ✓
operations += 2 → operations = 2
n = 12 / 2 = 6
6 % 2 = 0? YES ✓
operations += 2 → operations = 4
n = 6 / 2 = 3
3 % 2 = 0? NO
Move to next factor
factor = 3:
━━━━━━━━━━━━━━━━━━━━
3 % 3 = 0? YES ✓
operations += 3 → operations = 7
n = 3 / 3 = 1
1 % 3 = 0? NO
n = 1, done!
factor = 4, 5, 6, ...:
━━━━━━━━━━━━━━━━━━━━
n = 1, loop terminates
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: operations = 7 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Prime factorization: 12 = 2 × 2 × 3
Sum of factors: 2 + 2 + 3 = 7 ✓
Path verification:
1 → 2 (copy, paste) = 2 ops
2 → 4 (copy, paste) = 2 ops
4 → 12 (copy, paste, paste) = 3 ops
Total: 2 + 2 + 3 = 7 ✓
Why This Works - The Beautiful Math:
THEOREM: Minimum operations = Sum of prime factors
Proof idea:
1. To multiply by k, we need k operations:
- 1 copy + (k-1) pastes = k total
2. To get n = a × b optimally:
- Get a: minSteps(a) operations
- Multiply by b: b operations
- Total: minSteps(a) + b
3. Recursively apply:
n = p₁ × p₂ × ... × pₖ (prime factorization)
minSteps(n) = p₁ + minSteps(p₂ × ... × pₖ)
= p₁ + p₂ + minSteps(p₃ × ... × pₖ)
= p₁ + p₂ + ... + pₖ
4. This is optimal because:
- Breaking composite factors into primes never increases cost
- Example: Factor 6 = 2 + 4 = 2 + (2+2) = 6 ops
vs 6 = 2 × 3 = 2 + 3 = 5 ops (better!)
Prime factorization gives minimum! 🎯
📊 Complexity Analysis
Time Complexity: O(√n)
n = target number
Loop runs up to √n (all prime factors ≤ √n)
For each factor, divide n repeatedly
For n = 1000:
√1000 ≈ 32 iterations
Very fast! ⚡
Space Complexity: O(1)
Only a few variables
Constant space!
Optimal! ✓
📊 Approach Comparison
┌──────────────────────────────────────────────────────────────┐
│ 2 KEYS KEYBOARD - APPROACH COMPARISON │
├──────────────┬───────────┬───────────┬────────────┬──────────┤
│ Approach │ Time │ Space │ Clarity │Interview │
├──────────────┼───────────┼───────────┼────────────┼──────────┤
│ Recursion │ O(n²√n) │ O(n) │ High │ Start │
│ Memoization │ O(n×√n) │ O(n) │ Good │ Good │
│ Bottom-Up DP │ O(n×√n) │ O(n) │ Good │ Good │
│ Prime Factor │ O(√n) │ O(1) │ Best ✓ │ Best ✓ │
└──────────────┴───────────┴───────────┴────────────┴──────────┘
For interviews: Show DP approach, then optimize to prime factorization!
💻 Complete Working Code
class Solution {
public int minSteps(int n) {
return primeFactor(n);
}
// Approach 4: Prime Factorization - O(√n) time, O(1) space
private int primeFactor(int n) {
if (n == 1)
return 0;
int operations = 0;
for (int factor = 2; factor <= n; factor++) {
while (n % factor == 0) {
operations += factor;
n /= factor;
}
}
return operations;
}
// Approach 3: Bottom-Up DP - O(n×√n) time, O(n) space
private int dp(int n) {
if (n == 1)
return 0;
int[] dp = new int[n + 1];
dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = i;
for (int j = 2; j < i; j++) {
if (i % j == 0) {
dp[i] = Math.min(dp[i], dp[j] + i / j);
}
}
}
return dp[n];
}
// Approach 2: Memoization - O(n×√n) time, O(n) space
private int[] memo;
private int memoization(int n) {
memo = new int[n + 1];
Arrays.fill(memo, -1);
return helperMemo(n);
}
private int helperMemo(int n) {
if (n == 1)
return 0;
if (memo[n] != -1)
return memo[n];
int minOps = n;
for (int d = 2; d < n; d++) {
if (n % d == 0) {
minOps = Math.min(minOps, helperMemo(d) + n / d);
}
}
memo[n] = minOps;
return minOps;
}
// Approach 1: Pure Recursion - O(n²√n) time
private int recursion(int n) {
if (n == 1)
return 0;
int minOps = n;
for (int d = 2; d < n; d++) {
if (n % d == 0) {
minOps = Math.min(minOps, recursion(d) + n / d);
}
}
return minOps;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.minSteps(3) == 3);
System.out.println(s.minSteps(1) == 0);
System.out.println(s.minSteps(6) == 5);
System.out.println(s.minSteps(12) == 7);
}
}
🔑 Key Insights
The Recursive Structure:
KEY: To get n A's, must come from divisor d!
Why? Can only multiply what we have via copy-paste.
Recurrence:
minSteps(n) = min{ minSteps(d) + n/d } for all divisors d
This naturally leads to DP solution! 🔑
The Mathematical Pattern:
INSIGHT: Minimum operations = Sum of prime factors!
Why this works:
Optimal path multiplies by primes:
1 → p₁ → p₁×p₂ → ... → n
Each multiplication by p costs p operations
Total = p₁ + p₂ + ... = sum of prime factors
This is provably optimal! 🎯
Why Prime Factorization:
Composite factors can be broken down:
Example: n = 12
Using 6: cost = minSteps(6) + 2 = 5 + 2 = 7
Using 2,2,3: cost = 2 + 2 + 3 = 7
Same result! But prime path is direct!
Breaking to primes is always optimal!
Pattern Recognition:
This is a MATH problem disguised as DP!
DP works: O(n×√n)
Math works better: O(√n)!
Similar problems:
- Minimum operations with mathematical insight
- Prime factorization applications
- Greedy + Math optimization
Key: Recognize the mathematical pattern! 🎯
🎪 Memory Aid
"Come from divisors only!"
"minSteps(d) + n/d for all d|n!"
"Sum of prime factors = answer!"
"Math beats DP here!" ✨
⚠️ Common Mistakes
- ❌ Not understanding the recursive structure (why divisors?)
- ❌ Not recognizing overlapping subproblems
- ❌ Missing the prime factorization pattern
- ❌ Thinking you can come from non-divisors
- ❌ Forgetting that n = 1 requires 0 operations
✅ Interview Talking Points
"This problem has beautiful recursive structure.
Recursive Insight:
To get n A's, we must come from some divisor d.
Why? Because copy-paste can only multiply.
Recurrence:
minSteps(n) = min{ minSteps(d) + n/d }
for all divisors d of n
Base case: minSteps(1) = 0
DP Approach (O(n×√n)):
Build table from 1 to n
For each i, try all divisors j:
dp[i] = min(dp[i], dp[j] + i/j)
This works efficiently.
Mathematical Insight (O(√n)):
INSIGHT: Answer = sum of prime factors!
Why? Optimal path multiplies by primes:
1 → p₁ (cost p₁) → p₁×p₂ (cost p₂) → ... → n
Total cost = p₁ + p₂ + ... = sum of prime factors
Algorithm:
Find all prime factors of n
Sum them (with repetition)
Example: 12 = 2 × 2 × 3 → answer = 2+2+3 = 7
Complexity: O(√n) time, O(1) space
Much better than O(n×√n) DP!
This shows when MATH beats DP!"
📝 Quick Revision Notes
🎯 Core Concept
Problem: Get n A's using only Copy All and Paste. Start with 1 A. Minimum operations?
Recursive Insight: To get n, must come from divisor d. Cost = minSteps(d) + n/d.
Mathematical Insight: Minimum operations = Sum of prime factors!
⚡ Quick Implementation
public class Solution {
public int minSteps(int n) {
// return recursive(n);
// Integer[] memo = new Integer[n + 1];
// return topDown(n, memo);
return bottomUp(n);
}
private int bottomUp(int n) {
// step 1
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 0;
// step 3
for (int i = 2; i <= n; i++) {
int res = i;
for (int divisor = 1; divisor < i; divisor++) {
if (i % divisor == 0) {
res = Integer.min(res, dp[divisor] + i / divisor);
}
}
dp[i] = res;
}
// step 2
return dp[n];
}
private int topDown(int n, Integer[] memo) {
if (n == 1) {
return 0;
}
if (memo[n] != null) {
return memo[n];
}
int res = n;
for (int divisor = 1; divisor < n; divisor++) {
if (n % divisor == 0) {
res = Math.min(res, recursive(divisor) + n / divisor);
}
}
return memo[n] = res;
}
private int recursive(int n) {
// step 2: base case
// ops required to have 1 character on screen: 0
// as one character is already present on the screen.
if (n == 1) {
return 0;
}
// step 1: try all divisors of n
// worse case max is n or can keep Integer.MAX_VALUE
int res = n;
for (int divisor = 1; divisor < n; divisor++) {
if (n % divisor == 0) {
// Meaning: steps required to go from 1->12, 2->12, 3->12
// 1 -> 12: f(1) + 12/1 = 12 (1 copy + 11 paste)
// 2 -> 12: f(2) + 12/2 = 8 (1C,1P,1C(2As copied),5P) = 8
// 3 -> 12: f(3)+12/3 = 3+4 = 7 (copy 3As and paste 4 times)
// 4 -> 12: f(4)+12/4 = 4+3 = 7 (copy 4As and paste 3 times)
// From above, we need recursively find f(2), f(3), f(4) etc
res = Math.min(res, recursive(divisor) + n / divisor);
}
}
return res;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.minSteps(3) == 3);
System.out.println(s.minSteps(4) == 4);
System.out.println(s.minSteps(5) == 5);
System.out.println(s.minSteps(6) == 5);
System.out.println(s.minSteps(7) == 7);
}
}
Complexity: O(√n) time, O(1) space
🔑 Key Points
The Recursive Formula:
minSteps(n) = min{ minSteps(d) + n/d } for all divisors d of n
Base: minSteps(1) = 0
Why? To multiply from d to n costs n/d operations!
The Mathematical Magic:
n = 12 = 2 × 2 × 3
Prime factors: [2, 2, 3]
Sum: 2 + 2 + 3 = 7 operations ✓
Path: 1 → 2 (2 ops) → 4 (2 ops) → 12 (3 ops)
DP Alternative: O(n×√n) time, O(n) space
dp[i] = i; // worst case
for (int j = 2; j < i; j++) {
if (i % j == 0) {
dp[i] = min(dp[i], dp[j] + i/j);
}
}
💡 Recognition
See "copy all + paste" + "minimum operations" → Think divisors and factorization! - Recursive structure based on divisors - Math insight > DP approach - Prime factorization is the key
⚠️ Common Traps
- ❌ Not understanding why only divisors work
- ❌ Missing the recursive structure
- ❌ Not recognizing prime factorization pattern
- ❌ Forgetting n = 1 is special (0 operations)
🎉 Congratulations!
You've mastered 2 Keys Keyboard - where clear recursion leads to elegant math!
What You Learned:
✅ Recursive thinking - Must come from divisors
✅ Recurrence relation - minSteps(d) + n/d
✅ Pure recursion - Understanding the structure
✅ Memoization - Caching overlapping subproblems
✅ Bottom-up DP - O(n×√n) solution
✅ Prime factorization - O(√n) optimal solution
✅ Math > DP - Recognizing mathematical patterns
This is a perfect example of how understanding the recursive structure leads to both DP and elegant mathematical solutions! 🚀✨