2 Keys Keyboard - Solution & Explanation
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
Constraints:
1 <= n <= 1000
Approach Overview
Problem 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 1: Dynamic Programming Solution
This approach involves using a dynamic programming array where dp[i] represents the minimum number of operations required to achieve exactly i 'A's on the screen. The idea is to divide the problem into subproblems and solve each subproblem once to build up a solution for the original problem. For each integer i, if it can be obtained from j by first copying all from j and pasting (i/j-1) times, then dp[i] can be updated as dp[j] + i/j steps.
This C solution initializes an array of size n+1 to track minimum steps for each possible number of 'A's up to n. We iterate over each possible number of 'A's, checking for each j (where 1 <= j < i) if i can be entirely divided by j. If so, update dp[i] using dp[j] plus the number of pastes needed to reach i from j.
Complexity
Time Complexity: O(n^2) due to the nested loops for divisor checking.
Space Complexity: O(n) to store the dynamic programming array.
Approach 2: Mathematical Analysis with Prime Factors
The optimal strategy is based on a mathematical observation wherein the solution boils down to the prime factorization of n. Essentially, if you can find all factors of numbers up to n, the minimum operations needed are the sum of the prime factors of these numbers. Whenever you can make a sequence by repeating operations, using a simple Copy All and Paste enough times to reach a bigger number allows the number of operations to be minimized via multiplying smaller sequences.
This C solution employs a strategy of dividing n by its smallest divisor d (starting from 2) repeatedly, summing the divisor to count. This extracts all the prime factors and sums them for minimum operations.
Complexity
Time Complexity: O(√n) as it iterates over possible factors up to the square root of n.
Space Complexity: O(1) with constant auxiliary space usage.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Solution | Time Complexity: O(n^2) due to the nested loops for divisor checking. |
| Mathematical Analysis with Prime Factors | Time Complexity: O(√n) as it iterates over possible factors up to the square root of n. |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
2 Keys Keyboard - Leetcode 650 - Python • NeetCodeIO • 18,650 views views
Watch 9 more video solutions →Frequently Asked Questions
Is 2 Keys Keyboard easy or hard?
2 Keys Keyboard Python/Java solution
How to solve 2 Keys Keyboard in O(n)?
What is the best approach for 2 Keys Keyboard?
Is 2 Keys Keyboard asked at Google/Amazon/Meta?
What data structure is used in 2 Keys Keyboard?
What is the time complexity of 2 Keys Keyboard?
Ready to solve this problem?
Practice 2 Keys Keyboard with our built-in code editor and test cases.
Practice on FleetCode