In this guide, you will get 650. 2 Keys Keyboard LeetCode Solution with the best time and space complexity. The solution to Keys Keyboard problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
650. 2 Keys Keyboard LeetCode Solution in C++
class Solution {
public:
int minSteps(int n) {
if (n <= 1)
return 0;
// dp[i] := the minimum steps to get i 'A's
vector<int> dp(n + 1);
// Copy 'A', then paste 'A' i - 1 times.
iota(dp.begin(), dp.end(), 0);
for (int i = 2; i <= n; ++i)
for (int j = i / 2; j > 2; --j)
if (i % j == 0) {
dp[i] = dp[j] + i / j; // Paste dp[j] i / j times.
break;
}
return dp[n];
}
}; /* code provided by PROGIEZ */
650. 2 Keys Keyboard LeetCode Solution in Java
class Solution {
public int minSteps(int n) {
// dp[i] := the minimum steps to get i 'A's
int[] dp = new int[n + 1];
for (int i = 2; i <= n; ++i) {
dp[i] = i; // Copy 'A', then paste 'A' i - 1 times.
for (int j = i / 2; j > 2; --j)
if (i % j == 0) {
dp[i] = dp[j] + i / j; // Paste dp[j] i / j times.
break;
}
}
return dp[n];
}
} // code provided by PROGIEZ
650. 2 Keys Keyboard LeetCode Solution in Python
class Solution:
def minSteps(self, n: int) -> int:
if n <= 1:
return 0
# dp[i] := the minimum steps to get i 'A's
# Copy 'A', then paste 'A' i - 1 times.
dp = [i for i in range(n + 1)]
for i in range(2, n + 1):
for j in range(i // 2, 2, -1):
if i % j == 0:
dp[i] = dp[j] + i // j # Paste dp[j] i / j times.
break
return dp[n] # code by PROGIEZ
