2 Keys Keyboard: Prime Factorization Meets Dynamic Programming

You start with a single character A on a notepad. You can perform only two operations: Copy All (copies everything on the screen to the clipboard) and Paste (appends the clipboard contents to the screen). Given an integer n, find the minimum number of operations to get exactly n copies of A on the screen.

This is LeetCode 650: 2 Keys Keyboard. At first it looks like a tricky simulation problem, but the optimal strategy has an elegant mathematical structure: the answer is the sum of the prime factors of n.

Why this problem matters

This problem sits at the intersection of number theory and dynamic programming. It rewards you for thinking about the problem mathematically before reaching for a DP table. The insight that "sum of prime factors" gives you the minimum cost appears in several problems involving optimal decomposition. Once you see why composite factors are always worse than their prime breakdowns, you gain a mental model that transfers to problems like Integer Break and Perfect Squares.

It also teaches you that DP and math solutions are not mutually exclusive. You can solve this with a clean DP recurrence and then realize the DP is secretly computing the prime factorization. Understanding both angles makes the solution stick.

The approach

The core idea: to multiply the number of characters on screen by a factor p, you need exactly p operations (1 Copy All + p - 1 Pastes). Since any composite factor c = a * b satisfies a + b < a * b (when both a and b are greater than 1), you should always break composite factors into smaller pieces. The optimal decomposition is the prime factorization, and the minimum cost is the sum of those prime factors.

def min_steps(n):
    result = 0
    d = 2
    while d * d <= n:
        while n % d == 0:
            result += d
            n //= d
        d += 1
    if n > 1:
        result += n
    return result

Step-by-step walkthrough

Let us trace through n = 12 to see both the factorization and the operations.

The prime factorization of 12 is 2 * 2 * 3. The minimum operations are 2 + 2 + 3 = 7.

Here is what the operation sequence looks like:

1. Start with A (1 character on screen)
2. Copy All, Paste: screen becomes AA (2 characters, cost 2)
3. Copy All, Paste: screen becomes AAAA (4 characters, cost 2)
4. Copy All, Paste, Paste: screen becomes AAAAAAAAAAAA (12 characters, cost 3)

Total: 2 + 2 + 3 = 7 operations. Each prime factor corresponds to one "round" of copying and pasting.

For n = 1, the answer is 0 because A is already on the screen. For a prime number like n = 7, the only option is to copy once and paste 6 times, costing 7 operations total.

Complexity analysis

The outer loop runs while d * d <= n, so it iterates at most sqrt(n) times. Each inner loop iteration divides n by d, so the total number of divisions across all iterations is bounded by log(n). Space is constant since you only track the running sum and the current divisor.

If you use the DP approach instead, time becomes O(n * sqrt(n)) because for each value from 2 to n you check divisors up to sqrt(i). Space is O(n) for the DP array.

Edge cases to watch for

• n = 1: the answer is 0. The character is already on screen, no operations needed.
• n is prime: the answer equals n itself (1 Copy All + n - 1 Pastes). There is no way to break it into cheaper steps.
• n is a power of 2: for example n = 8 gives 2 + 2 + 2 = 6. Each step doubles the count, and doubling is the cheapest repeated operation.
• Large n with small prime factors: n = 1000 = 2 * 2 * 2 * 5 * 5 * 5 gives 2 + 2 + 2 + 5 + 5 + 5 = 21. Many small factors keep the cost low.

The building blocks

This problem is built on the prime factorization decomposition pattern. The key insight is that any multiplicative decomposition has a cost equal to the sum of its factors, and prime factors minimize that sum. This same reasoning appears in:

• Integer Break (LeetCode 343): decompose a number into parts to maximize their product. The optimal pieces are 3s and 2s, which are the building blocks of multiplicative optimization.
• Perfect Squares (LeetCode 279): find the minimum number of perfect squares that sum to n. Instead of multiplicative decomposition, it uses additive decomposition with square "denominations."
• Count Primes (LeetCode 204): the sieve-based prime counting problem. Understanding prime factorization here directly helps you reason about that problem too.

The shared theme is that problems involving factors, multiples, and decompositions often reduce to understanding the prime structure of the input.

From understanding to recall

The solution here is short, but reproducing it under pressure requires remembering several pieces: why the answer is the sum of prime factors, why composite factors are always suboptimal, how to implement trial division cleanly, and how to handle the remaining factor after the loop. Each of those is a small but distinct piece of knowledge.

Spaced repetition helps you internalize these pieces one at a time. You revisit the problem at increasing intervals, write the factorization loop from memory, and verify the edge cases. After a few reps, the connection between "2 Keys Keyboard" and "sum of prime factors" becomes automatic. That is the difference between recognizing a solution when you see it and being able to produce it in an interview.

Related posts

• Integer Break - The closest sibling: same multiplicative decomposition thinking, different optimization objective
• Perfect Squares - Additive decomposition DP that shares the "minimize cost of reaching n" structure
• Count Primes - Prime number fundamentals that directly support the factorization approach used here