Watch 10 video solutions for 2 Keys Keyboard, a medium level problem involving Math, Dynamic Programming. This walkthrough by NeetCodeIO has 18,377 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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
Constraints:
1 <= n <= 1000Problem Overview: Start with one character 'A' on a notepad. Two operations are allowed: Copy All and Paste. The task is to reach exactly n characters using the minimum number of operations.
Approach 1: Dynamic Programming (O(n^2) time, O(n) space)
Define dp[i] as the minimum operations required to produce i characters. To build i, you must copy some earlier count j and paste multiple times. If j divides i, you can copy j once and paste (i / j - 1) times. Iterate through all possible divisors j of i and update dp[i] = min(dp[i], dp[j] + i / j). The key idea is recognizing that building i efficiently depends on reusing a previously constructed block size. This approach demonstrates classic dynamic programming where larger states reuse smaller computed results.
Approach 2: Mathematical Analysis with Prime Factors (O(sqrt n) time, O(1) space)
The optimal strategy corresponds to breaking n into multiplicative steps. Each factor represents one Copy All followed by several Paste operations. For example, producing 9 characters works best as 3 × 3: build 3, copy, then paste twice. The total operations equal the sum of prime factors of n. Repeatedly divide n by its smallest factor starting from 2 and accumulate the factor values. This works because any composite multiplication sequence can be decomposed into smaller prime multipliers that minimize operations. The solution relies on number theory concepts from math and prime factorization.
Recommended for interviews: The mathematical prime factor solution is the expected optimal answer because it reduces the complexity to O(sqrt n) with constant space. However, explaining the dp[i] formulation first shows clear reasoning about the state transition and the effect of copy–paste operations. Many interviewers appreciate seeing the dynamic programming approach before simplifying it into the mathematical insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n^2) | O(n) | When deriving the solution step‑by‑step or explaining the transition logic in interviews |
| Prime Factor Mathematical Approach | O(sqrt n) | O(1) | Optimal solution for large n using number theory insight |