2 Keys Keyboard Solution

Problem

You start with a notepad that has exactly one 'A' on it. In each operation you can either Copy All (copies everything currently on screen to the clipboard) or Paste (writes the clipboard contents again). Find the minimum number of operations needed to produce exactly n copies of 'A'.

Example:

Input: n = 6
Output: 5
Explanation: Copy All → Paste (→ "AA") → Paste (→ "AAA") → Copy All → Paste (→ "AAAAAA") — 5 operations total.

Counter-example (why greedy fails): For n = 6, repeatedly pasting from a single Copy All takes 6 operations (copy once, paste 5 times). Copying at "AAA" instead and pasting once reaches the target in only 5.

Intuition

Every useful sequence of moves breaks into segments: one Copy All followed by some number of Pastes that multiply the current count by a fixed integer. Reaching n from 1 means chaining multiplications whose product is n. The total operations equal the sum of those multipliers — and the sum-minimizing way to factor any integer is to use its prime factors. This reduces the optimal solution to prime factorization.

Approach 1 — Dynamic Programming

Build a table where dp[i] holds the minimum operations to end up with exactly i 'A's. For every divisor j of i, we can first reach j 'A's and then pay i/j more steps (1 Copy All plus i/j − 1 Pastes) to multiply up to i.

Steps:

Allocate dp of size n + 1; initialize all entries to infinity.
Set dp[1] = 0 — you already have one 'A' at no cost.
For each count i from 2 to n:
For each potential base j from 1 to i // 2:
If j divides i, update dp[i] = min(dp[i], dp[j] + i // j).
Return dp[n].

1def minSteps(n: int) -> int:
2    dp = [float('inf')] * (n + 1)
3    dp[1] = 0  # already have one 'A', zero operations needed
4
5    for count in range(2, n + 1):
6        for base in range(1, count // 2 + 1):
7            if count % base == 0:  # base is a valid "last copy point"
8                dp[count] = min(dp[count], dp[base] + count // base)
9
10    return dp[n]

Time: O(n²) — for each of the n counts we scan up to n/2 potential divisors
Space: O(n) — the dp array stores one value per possible count

Approach 2 — Prime Factorization

The minimum operations equals the sum of n's prime factors (with repetition). For each prime factor p, you need exactly p operations: 1 Copy All to lock in the current buffer, then p − 1 Pastes to multiply the count by p.

Steps:

Initialize total_steps = 0 and start testing factor = 2.
While factor * factor ≤ n, check if factor divides n.
Whenever it does, add factor to total_steps and divide n by factor (repeat until no longer divisible).
Increment factor and continue.
If n > 1 after the loop, n itself is a remaining prime factor — add it to total_steps.

1def minSteps(n: int) -> int:
2    total_steps = 0
3    factor = 2
4
5    while factor * factor <= n:
6        while n % factor == 0:
7            total_steps += factor  # each occurrence of this prime costs 'factor' ops
8            n //= factor
9        factor += 1
10
11    if n > 1:
12        total_steps += n  # n is itself prime; one Copy All + (n-1) Pastes
13
14    return total_steps

Time: O(√n) — the outer loop only needs to reach √n since any factor above √n must be prime
Space: O(1) — no auxiliary data structures needed

Complexity Summary

Approach	Time	Space	When to use
Dynamic Programming	O(n²)	O(n)	Readable baseline; derive it first in an interview before optimizing
Prime Factorization	O(√n)	O(1)	Optimal when n can be large or you've recognized the number-theory connection

Common Mistakes

Setting dp[1] = 1 instead of 0: You start with one 'A' already on screen — reaching count 1 requires zero operations, not one.
Starting the inner divisor loop at 2: Skipping base = 1 drops the path of copying once and pasting n − 1 times, which is the only valid path when n is prime and produces incorrect results for primes.
Forgetting the remaining factor after the outer loop: When n is prime (e.g., n = 7), the while condition factor * factor <= n is never satisfied for that prime, so it never gets divided out. The if n > 1 guard is essential.
Confusing Paste with "add 1": Each Paste copies the entire clipboard, not a single character. The transition cost is count / base (the multiplication factor), not count - base.
Thinking the answer for prime p is p − 1: You need 1 Copy All to load the buffer before pasting, so the cost is 1 + (p − 1) = p total operations.

2 Keys Keyboard — Solution