2 Keys Keyboard

2 Keys Keyboard

What is this problem about?

In the 2 Keys Keyboard coding problem, you start with a single character 'A' on a screen. You can perform only two operations:

1. Copy All: Copy all characters currently on the screen.
2. Paste: Paste the characters you last copied. The goal is to find the minimum number of operations to reach exactly $n$ characters.

Why is this asked in interviews?

This question is a favorite at Uber and Google because it looks like a Dynamic Programming problem but can be cleverly simplified using Math (Prime Factorization). It tests whether a candidate can look past the immediate "coding" challenge to find an underlying mathematical pattern.

Algorithmic pattern used

This problem fits both the Dynamic Programming interview pattern and Math/Greedy logic. The core insight is that to get $n$ characters, you are essentially breaking $n$ into its prime factors. For example, to get 6 'A's, you could get 2 'A's (Copy + Paste = 2 ops) and then treat that block as a unit to get 3 of them (Copy + Paste + Paste = 3 ops). Total = 5 operations.

Example explanation

If $n = 9$:

• Start with 'A'.
• Copy All, Paste, Paste (3 ops) $\rightarrow$ gives "AAA".
• Copy All, Paste, Paste (3 ops) $\rightarrow$ gives "AAAAAAAAA". Total = 6 operations. Notice $9 = 3 \times 3$, and $3 + 3 = 6$.

Common mistakes candidates make

• Over-engineering DP: While DP works, a simple prime factorization loop is much faster and uses $O(1)$ space.
• Miscounting operations: Forgetting that "Copy All" is itself an operation that must be performed before "Paste."
• Not recognizing prime cases: If $n$ is prime (like 7), the only way to reach it is to copy the 1st 'A' and paste it 6 times ($1 + 6 = 7$ ops).

Interview preparation tip

If a problem involves building up to a number using multiplication-like steps, check if the sum of prime factors is the answer. It’s a common shortcut in competitive programming.