2 Keys Keyboard — Solution in Python, Java & C++
2 Keys Keyboard solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
2 Keys Keyboard is a medium coding problem on dynamic programming and math, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Dynamic Programming, Math
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A notepad starts with a single character A. Two operations are available:
- Copy All — copy every character currently on the notepad (a partial copy is not allowed).
- Paste — append whatever was last copied.
Given an integer n, return the minimum number of operations needed to end up with exactly n copies of A.
Example 1
Input: n = 3
Output: 3
Explanation: Copy All, Paste, Paste.
Example 2
Input: n = 1
Output: 0
Explanation: The single A is already there.
Example 3
Input: n = 9
Output: 6
Constraints
1 <= n <= 1000
Hints for 2 Keys Keyboard
Hint 1
The notepad's length can only ever be multiplied by a whole number, so the last Copy All happened at some divisor
dofn.Hint 2
Going from
dtoncosts one Copy All plusn / d - 1Pastes — that isn / doperations.Hint 3
So
dp[n] = min over divisors d of (dp[d] + n / d), and the answer equals the sum ofn's prime factors.
How to solve 2 Keys Keyboard
The notepad's length is only ever multiplied, so reaching n from a divisor d costs n / d operations (one copy plus n/d - 1 pastes). The minimum is the sum of n's prime factors.
Approach
- Trial-divide
nby2, 3, 4, …; for each factorfthat divides, addfand divide it out. - Add any prime remainder greater than 1.
Why it works
Multiplying by a composite ab costs ab operations while multiplying by a then b costs a + b ≤ ab, so splitting into primes is never worse. The dp[n] = min over divisors d (dp[d] + n/d) recurrence reaches the same sum.
Complexity
- Time —
O(√n) - Space —
O(1)
Pitfalls
n = 1needs zero operations, which the loop handles because nothing divides.
Reference solution
Python
def minSteps(n: int) -> int:
steps = 0
factor = 2
while factor * factor <= n:
while n % factor == 0:
steps += factor
n //= factor
factor += 1
if n > 1:
steps += n
return stepsJava
public static int minSteps(int n) {
int steps = 0;
for (int factor = 2; factor * factor <= n; factor++) {
while (n % factor == 0) {
steps += factor;
n /= factor;
}
}
if (n > 1) steps += n;
return steps;
}C++
int minSteps(int n) {
int steps = 0;
for (int factor = 2; factor * factor <= n; factor++) {
while (n % factor == 0) {
steps += factor;
n /= factor;
}
}
if (n > 1) steps += n;
return steps;
}JavaScript
var minSteps = function(n) {
let steps = 0;
for (let factor = 2; factor * factor <= n; factor++) {
while (n % factor === 0) {
steps += factor;
n /= factor;
}
}
if (n > 1) steps += n;
return steps;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming