Last updated on January 13th, 2025 at 03:27 am
Here, we see a 2 Keys Keyboard LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Companies
Microsoft
Level of Question
Medium
2 Keys Keyboard LeetCode Solution
Table of Contents
1. 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
2. Coding Pattern Used in Solution
The problem in all four implementations revolves around finding the minimum number of steps to generate a string of length n using only two operations: Copy All and Paste. This problem can be categorized under the Dynamic Programming pattern, as all implementations use some form of memoization or tabulation to optimize the solution by avoiding redundant calculations.
3. Code Implementation in Different Languages
3.1 2 Keys Keyboard C++
class Solution {
public:
int minSteps(int n) {
if(n == 1) return 0;
int count = 0;
bool *isPrime = new bool[n + 1];
for(int i = 2; i < n + 1; i++) isPrime[i] = true;
for(int i = 2; i < n + 1; i++)
{
if(isPrime[i] == true)
{
while(n % i == 0)
{
count += i;
n /= i;
}
for(int j = i * i; j < n + 1; j += i)
{
if(isPrime[j]) isPrime[j] = false;
}
}
}
return count;
}
};
3.2 2 Keys Keyboard Java
class Solution {
public int minSteps(int n) {
Integer[][] dp = new Integer[n + 1][n + 1];
return countSteps(n, 0, 1, 0, dp);
}
private int countSteps(int n, int clipBoard, int document, int steps, Integer[][] cache) {
if (document == n) {
return steps;
}
if (document > n || clipBoard > n) return Integer.MAX_VALUE;
if (cache[clipBoard][document] != null) return cache[clipBoard][document];
int copy = Integer.MAX_VALUE;
int paste = Integer.MAX_VALUE;
if (document != clipBoard) {
copy = countSteps(n, document, document, steps + 1, cache);
}
if (clipBoard > 0)
paste = countSteps(n, clipBoard, document + clipBoard, steps + 1, cache);
cache[clipBoard][document] = Math.min(copy, paste);
return cache[clipBoard][document];
}
}
3.3 2 Keys Keyboard JavaScript
var minSteps = function(n) {
const dp = new Array(n + 1).fill(0);
dp[0] = 0;
dp[1] = 0;
for (let i = 2; i <= n; i++) {
dp[i] = i;
for (let j = Math.floor(i / 2); j >= 1; j--) {
if (i % j === 0) {
dp[i] = dp[j] + (i / j);
break;
}
}
}
return dp[n];
};
3.4 2 Keys Keyboard Python
class Solution(object):
def minSteps(self, n):
cache = {}
def helper(screen, clipboard):
if (screen, clipboard) in cache: return cache[(screen, clipboard)]
if screen == n: return 0
if screen > n: return float("Inf")
copy_paste = helper(screen+screen, screen) + 2
paste = float("Inf")
if clipboard:
paste = helper(screen + clipboard, clipboard) + 1
cache[(screen, clipboard)] = min(copy_paste, paste)
return cache[(screen, clipboard)]
return helper(1, 0)
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n log log n) | O(n) |
| Java | O(n²) | O(n²) |
| JavaScript | O(n²) | O(n) |
| Python | O(n²) | O(n²) |
The problem is best categorized under the Dynamic Programming pattern, with variations in implementation:
- C++: Prime Factorization (a mathematical approach).
- Java, JavaScript, Python: Dynamic Programming (recursive memoization or bottom-up tabulation).