443. 2 Keys Keyboard
You are editing a note that currently shows a single character A. Only two moves are available:
- Copy All — copy every character currently on screen to the clipboard, replacing whatever the clipboard held before. You can never copy just part of the screen.
- Paste — append the clipboard's contents to the end of the screen. The clipboard keeps its contents afterwards.
Given an integer n, return the minimum total number of moves needed for the screen to show exactly n copies of A.
If n = 1 the screen is already correct and the answer is 0.
Example 1:
Input: n = 3
Output: 3
Explanation: Copy All (clipboard = A), Paste (screen = AA), Paste (screen = AAA). Three moves and no shorter sequence exists.
Example 2:
Input: n = 1
Output: 0
Explanation: The single A is already on screen, so zero moves are needed.
Constraints:
- 1 ≤ n ≤ 1000
Hints:
After you press Copy All at some count d, every later count is a multiple of d — pasting only ever adds d more. So reaching n means multiplying the count by whole-number factors, one block at a time.
Multiplying the current count by f costs exactly f moves: one Copy All plus f − 1 Pastes. So if n = f1 · f2 · … · fk, the total cost is f1 + f2 + … + fk. Which factorization has the smallest sum? Note a · b >= a + b whenever a, b >= 2 — splitting composite factors never hurts, so split all the way down to primes.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 3
Expected output: 3