Leetcode 650. 2 Keys Keyboard
Problem Explanation
The problem is about finding the minimum number of steps to get exactly n
number of A
on a notepad, where the only two operations allowed are Copy All
and Paste
. This means, initially we have a notepad with a single character A
and you have to achieve n
number of A
s on the notepad by using Copy All
and Paste
operations in the least possible number of steps.
As an example, if the input n
is 3
, the steps would be:
Copy All
operation to copy the singleA
on the notepad.Paste
operation to yieldAA
.- Second
Paste
operation to getAAA
.
Hence, the minimum number of steps to get n = 3
is 3
.
The range of n
will be between 1
to 1000
.
Now, let's look at the solution approach and how it uses dynamic programming to solve this problem.
Solution Approach
This problem is a classic example of a dynamic programming problem. Here we start by initializing an array dp
of size n + 1
where dp[i]
indicates the minimum steps to get i
number of A
s.
The array dp
is initialized in such a way that dp[i]
is i
for all i
as in the worst case we can get i
number of A
s by doing Copy All
and Paste
i-1
times.
Then, we iterate from 2
to n
and for each i
, perform a nested iteration from i / 2
to 2
in descending order. If i
is divisible by j
, we update dp[i]
as dp[j] + i / j
. Finally, dp[n]
will have our result.
Here, the idea is if i
is divisible by j
then we can get i
number of A
s by copying the j
number of A
s and pasting it i / j
times.
Python Solution
Here is the equivalent Python solution:
1 2python 3class Solution: 4 def minSteps(self, n: int) -> int: 5 if n <= 1: 6 return 0 7 8 dp = [i for i in range(n + 1)] 9 10 for i in range(2, n + 1): 11 for j in range(i // 2, 2, -1): 12 if i % j == 0: 13 dp[i] = dp[j] + i // j 14 break 15 return dp[n]
Java Solution
1 2java 3class Solution { 4 public int minSteps(int n) { 5 int[] dp = new int[n + 1]; 6 7 for (int i = 0; i <= n; i++) { 8 dp[i] = i; 9 } 10 11 for (int i = 2; i <= n; i++) { 12 for (int j = i / 2; j > 2; --j) { 13 if (i % j == 0) { 14 dp[i] = dp[j] + i / j; 15 break; 16 } 17 } 18 } 19 return dp[n]; 20 } 21}
JavaScript Solution
1 2javascript 3var minSteps = function(n) { 4 let dp = Array(n + 1).fill(0).map((_, i) => i); 5 6 for (let i = 2; i <= n; i++) { 7 for (let j = Math.floor(i / 2); j > 2; j--) { 8 if (i % j === 0) { 9 dp[i] = dp[j] + i / j; 10 break; 11 } 12 } 13 } 14 return dp[n]; 15};
C++ Solution
1 2c++ 3class Solution { 4public: 5 int minSteps(int n) { 6 vector<int> dp(n+1); 7 iota(dp.begin(), dp.end(), 0); 8 9 for (int i = 2; i <= n; i++) { 10 for (int j = i / 2; j > 2; --j) { 11 if (i % j == 0) { 12 dp[i] = dp[j] + i / j; 13 break; 14 } 15 } 16 } 17 return dp[n]; 18 } 19};
C# Solution
1 2csharp 3public class Solution { 4 public int MinSteps(int n) { 5 int[] dp = new int[n+1]; 6 for(int i=0; i <= n; i++) { 7 dp[i] = i; 8 } 9 for(int i=2; i <= n; i++) { 10 for(int j=i/2; j > 2; --j) { 11 if(i % j == 0) { 12 dp[i] = dp[j] + i / j; 13 break; 14 } 15 } 16 } 17 return dp[n]; 18 } 19}
Complexity Analysis
All our solutions have time and space complexity of O(n^2) and O(n), respectively.
The time complexity is O(n^2) because of the nested iteration. The outer iteration is from 2 to n and the inner iteration is from i / 2 to 2. Hence, the total time complexity gets O(n^2).
The space complexity is O(n) because of the storage array dp
of size n + 1
that is being used.
Concluding
With initially only one character A
, achieving n
number of A
s by using the least possible number of Copy All
and Paste
operations might seem like a plain brute force approach. However, through the use of dynamic programming, the problem becomes more of locating the smallest possible divisor. The speed and efficiency of dynamic programming speeds up calculations, reducing the search space required and leveraging previously-computed results.
Therefore, the problem is a great practice to understand and implement dynamic programming. Furthermore, the problem can be solved using dynamic programming in Python, JavaScript, C++, and other languages, showing the wide application of dynamic programming in different programming languages.
The key takeaway from this problem is to familiarize yourself with dynamic programming and apply it in suitable scenarios where it can significantly decrease the time complexity. It's also an excellent illustration of how much time and space complexity can be saved by using more advanced data manipulation techniques, specifically through dynamic programming. This problem should encourage you to think about how you can use dynamic programming to optimize your own coding challenges or when trying to optimize time and space in real-world tasks such as these.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.