Skip to main content

650. 2 Keys Keyboard

medium

Starting from one A on the screen, find the minimum operations (copy-all + paste) to display exactly n As. DP reduces to summing the prime factors of n.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 (copy all the characters present on the screen), or Paste (paste the characters which were copied last time). Given an integer n, return the minimum number of operations to get the character 'A' exactly n times on the screen.

Constraints

  • 1 <= n <= 1000

Examples

Example 1

Input
n = 3
Output
3

Explanation: Copy All, Paste, Paste — 3 operations to get AAA.

Example 2

Input
n = 1
Output
0

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

If you have k As and do Copy All + (m-1) Pastes, you reach k * m As in m operations.

Hint 2

Define dp[i] = min operations to get i As. dp[i] = min over divisors j of i of (dp[j] + i / j).

Hint 3

The answer equals the sum of prime factors of n (counted with multiplicity).

Solution approach

Reveal approach

Define the subproblem dp[i] = minimum operations to reach exactly i As. To land on i, the last 'Copy All' must have happened at some divisor j of i (so the screen had j As), followed by (i / j - 1) pastes, totaling i / j operations after reaching j. The recurrence relation is dp[i] = min over divisors j of i (1 <= j < i) of dp[j] + i / j. Base case dp[1] = 0. Iterate i from 2 to n; for each i, walk divisors up to sqrt(i) and update dp[i]. Return dp[n]. The optimal substructure aligns with prime factorization: dp[n] equals the sum of n's prime factors with multiplicity, because for any composite step k * m the operations decompose as dp[k] + m and recursing reveals each prime factor contributes itself to the total. Time O(n * sqrt(n)), space O(n).

Complexity

Time
O(n * sqrt(n))
Space
O(n)

Related patterns

  • dynamic-programming
  • memoization-recursion

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Microsoft

Practice these live with InterviewChamp.AI

Drill 2 Keys Keyboard and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →