2 Keys Keyboard
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
A classic approach for optimization problems like this is Dynamic Programming. We can define a subproblem as finding the minimum steps to get i 'A's, let's call this dp[i]. To compute dp[n], we can think about the last operation. It must have been a 'Paste'. If we pasted k characters, the screen must have had n-k characters before. This line of thought is complicated. A better way is to realize that to get n characters by pasting, we must have copied some number of characters j that is a divisor of n. The number of operations to go from j characters to n characters is n/j (1 for Copy, and n/j - 1 for Paste). This gives us the recurrence relation: dp[n] = min(dp[j] + n/j) for all j that are divisors of n.
Algorithm
- Create a
dparray of sizen + 1, wheredp[i]will store the minimum number of operations to geticharacters. - Initialize
dp[1] = 0. For all otheri, initializedp[i] = i, which represents the worst-case scenario (copying 'A' once and pastingi-1times). - Iterate from
i = 2ton. - For each
i, iterate through its possible divisorsjfrom1up toi/2. - If
jis a divisor ofi, it means we can obtainicharacters fromjcharacters. This involves one 'Copy All' operation on thejcharacters and then(i/j) - 1'Paste' operations. The total number of operations for this step isi/j. - The total operations to get
icharacters via this path isdp[j] + i/j. - Update
dp[i]with the minimum value found:dp[i] = min(dp[i], dp[j] + i/j). - After the loops complete,
dp[n]will hold the minimum number of operations.
Walkthrough
We can build the solution iteratively from the bottom up. We'll use an array, dp, where dp[i] stores the minimum steps to achieve i 'A's. The base case is dp[1] = 0 since we start with one 'A'. For any number i, the most straightforward (but not necessarily optimal) way to get i 'A's is to copy the initial 'A' and paste it i-1 times, taking i steps. We use this as an initial value for dp[i]. Then, we try to find a better solution. To get i 'A's, we must have previously had j 'A's on the screen, where j is a divisor of i. We would then copy the j 'A's and paste them (i/j) - 1 times. This sequence of a copy and multiple pastes takes i/j operations. So, the total steps would be dp[j] + i/j. We check this for all divisors j of i and take the minimum.
class Solution { public int minSteps(int n) { if (n == 1) { return 0; } int[] dp = new int[n + 1]; for (int i = 2; i <= n; i++) { dp[i] = i; // Initialize with the worst-case (copy 'A', paste i-1 times) for (int j = i / 2; j >= 1; j--) { if (i % j == 0) { // To get i 'A's from j 'A's, it takes i/j operations. // (1 Copy + (i/j - 1) Pastes) dp[i] = Math.min(dp[i], dp[j] + i / j); } } } return dp[n]; }}Complexity
Time
O(n^2) - We have two nested loops. The outer loop runs from `i = 2` to `n`, and the inner loop runs from `j = i/2` to `1`. The total number of operations is roughly the sum of `i/2` for `i` from 2 to `n`, which is proportional to `n^2`.
Space
O(n) - We use a DP array of size `n+1` to store the results of subproblems.
Trade-offs
Pros
Relatively straightforward to understand and implement.
Correctly solves the problem for the given constraints.
Cons
The time complexity of O(n^2) can be too slow if
nis very large.Requires O(n) space, which might be an issue for very large
n.
The previous DP approach can be optimized. Instead of iterating through i and finding all its divisors j to compute dp[i], we can flip the logic. We can iterate through i and use dp[i] to update the dp values for all multiples of i. For a given i, we can reach 2*i, 3*i, 4*i, etc. Reaching j*i from i takes j operations (one copy and j-1 pastes). This way, each pair (i, j) is considered exactly once, leading to a more efficient calculation.
Algorithm
- Create a
dparray of sizen + 1. - Initialize
dp[i] = ifori > 1anddp[1] = 0. - Iterate with
ifrom1ton. - For each
i, we consider it as a building block. We can generate multiples ofiby copying theicharacters and pasting them. - Start an inner loop with a multiplier
jfrom 2. The target number of characters will bem = i * j. - As long as
m <= n, we can potentially updatedp[m]. The number of steps to getmfromiisj(1 copy,j-1pastes). The total steps aredp[i] + j. - We update
dp[m] = min(dp[m], dp[i] + j). - After the loops,
dp[n]contains the result.
Walkthrough
This approach also uses a bottom-up dynamic programming strategy but with a more efficient state transition. We create a dp array of size n+1. We can initialize dp[i] to i (the worst-case steps) for i > 1, and dp[1] = 0. Then, we iterate from i = 1 up to n. For each i, we iterate through multiples i*j (where j starts from 2). The cost to get i*j 'A's from i 'A's is j operations. So, we can update the minimum steps for i*j as dp[i*j] = min(dp[i*j], dp[i] + j). This process resembles the Sieve of Eratosthenes, where we proactively update future values based on the current one.
class Solution { public int minSteps(int n) { if (n == 1) { return 0; } int[] dp = new int[n + 1]; // dp[1] is 0 by default for (int i = 2; i <= n; i++) { dp[i] = i; // Initialize with worst case } for (int i = 1; i <= n / 2; i++) { for (int j = 2; i * j <= n; j++) { dp[i * j] = Math.min(dp[i * j], dp[i] + j); } } return dp[n]; }}Complexity
Time
O(n log n) - The total number of operations is the sum of `n/i` for `i` from 1 to `n`. This sum is `n * (1/1 + 1/2 + ... + 1/n)`, which is `n` times the n-th Harmonic number. The Harmonic series is approximately `log n`, so the complexity is `O(n log n)`.
Space
O(n) - We use a DP array of size `n+1`.
Trade-offs
Pros
More efficient time complexity than the basic DP approach.
Still a systematic DP approach that is guaranteed to find the optimal solution.
Cons
Still requires O(n) space.
While more efficient than the basic DP, it's not the optimal solution.
The most efficient solution comes from a mathematical observation about the problem's structure. The minimum number of operations to get n 'A's is simply the sum of the prime factors of n (with multiplicity). For example, to get n = 12 'A's, the prime factorization is 2 * 2 * 3. The minimum steps are 2 + 2 + 3 = 7. This can be reasoned by considering that to get n = p * m characters, where p is a prime, the most efficient way is to first get m characters and then apply one 'Copy' and p-1 'Paste' operations, adding p steps. Applying this recursively, the total cost becomes the sum of all prime factors.
Algorithm
- Handle the base case: if
nis 1, return 0. - Initialize a variable
steps = 0to accumulate the sum of prime factors. - Iterate with a divisor
dstarting from 2, as long asd*d <= n. - Inside the loop, use a
whileloop to check ifdis a factor of the currentn. - While
n % d == 0, it meansdis a prime factor. Adddtostepsand updatenby dividing it byd(n = n / d). - After the inner
whileloop, incrementdto check the next potential factor. - After the main loop finishes, if
nis still greater than 1, it means the remaining value ofnis a prime factor itself (e.g., if the originalnwas 14, after dividing by 2,nbecomes 7, and the loop fordends atd=2. The remainingn=7must be added). - Add the remaining
ntosteps. - Return
steps.
Walkthrough
This approach transforms the problem from a dynamic programming puzzle into a number theory problem: finding the sum of prime factors of n. We can implement a standard prime factorization algorithm. We start with a divisor d=2. We repeatedly divide n by d as long as it's divisible, adding d to our total steps for each successful division. Once n is no longer divisible by d, we increment d and repeat. We only need to check for divisors up to sqrt(n). If, after this process, n is still greater than 1, the remaining n must be a prime factor itself, so we add it to our total.
class Solution { public int minSteps(int n) { int steps = 0; for (int d = 2; d * d <= n; d++) { while (n % d == 0) { steps += d; n /= d; } } if (n > 1) { steps += n; } return steps; }}Complexity
Time
O(sqrt(n)) - The algorithm performs trial division to find prime factors, which only needs to check for divisors up to the square root of `n`.
Space
O(1) - We only use a few variables to store the running sum and the current state of `n`.
Trade-offs
Pros
Extremely efficient with O(sqrt(n)) time complexity.
Requires only O(1) space.
Simple and concise code.
Cons
The logic relies on a mathematical insight which might not be immediately obvious during an interview.
Solutions
Solution
class Solution {public int minSteps(int n) { int res = 0; for (int i = 2; n > 1; ++i) { while (n % i == 0) { res += i; n /= i; } } return res; }}class Solution {public: vector<int> f; int minSteps(int n) { f.assign(n + 1, -1); return dfs(n); } int dfs(int n) { if (n == 1) return 0; if (f[n] != -1) return f[n]; int ans = n; for (int i = 2; i * i <= n; ++i) { if (n % i == 0) { ans = min(ans, dfs(n / i) + i); } } f[n] = ans; return ans; }};class Solution: def minSteps(self, n: int) -> int: @ cache def dfs(n): if n == 1: return 0 i, ans = 2, n while i * i <= n: if n % i == 0: # factor `i` can be used as the number of modules # n // i, length of the module `n/i` ans = min ( ans , dfs ( n // i ) + i ) i += 1 return ans return dfs ( n ) ############ # iteration class Solution : def minSteps ( self , n : int ) -> int : res = 0 i = 2 while n > 1 : while n % i == 0 : res += i n //= i i += 1 return res ############ """ 1. group operations as ([^C][^V][^V]...[^V]) that has in total k operations and it gets k * # of A 2. n can be written as x_1 * x_2 * ... * x_N 3. then total operations # = x_1 + x_2 + ... + x_N 4. since p * q >= p + q for integers > 1, to min the result 5. decomposite x_1 to x_N to min the sum """ ''' `yield` is a keyword that is used like return, except the function will return a generator. https://stackoverflow.com/questions/231767/what-does-the-yield-keyword-do-in-python ''' class Solution ( object ): def _minSteps ( self , n ): """ :type n: int :rtype: int """ if n == 1 : return 0 for i in range ( 2 , int (( n + 1 ) ** 0.5 ) + 1 ): if n % i == 0 : return i + self . minSteps ( n / i ) return n def minSteps ( self , n ): def factor ( n ): d = 2 while d * d <= n : while n % d == 0 : n /= d yield d d += 1 if n > 1 : yield n return sum ( factor ( n ))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.