2 Keys Keyboard

Medium
338.

2 Keys Keyboard

2 Keys Keyboard is a medium coding problem on dynamic programming and math, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var minSteps = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    The notepad's length can only ever be multiplied by a whole number, so the last Copy All happened at some divisor d of n.

  2. Hint 2

    Going from d to n costs one Copy All plus n / d - 1 Pastes — that is n / d operations.

  3. Hint 3

    So dp[n] = min over divisors d of (dp[d] + n / d), and the answer equals the sum of n'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

  1. Trial-divide n by 2, 3, 4, …; for each factor f that divides, add f and divide it out.
  2. 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 = 1 needs 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 steps

Java

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