Classic problem #650MediumMathDynamic Programming
2 Keys Keyboard
Real-world version: Fewest Presses to Reach n CopiesTracked in this browser only
Read 2 Keys Keyboard on LeetCode(opens in a new tab)
The statement here is our own: the same inputs, outputs and technique.
A sheet starts with a single mark on it and the clipboard empty. Two keys are available:
- copy all: replace the clipboard with everything currently on the sheet;
- paste: append the clipboard's contents to the sheet.
Return the fewest key presses that leave exactly n marks on the sheet.
Examples
Example 1
- Input
- n = 6
- Output
- 5
Copy and paste once reaches two marks in two presses, then copy and paste twice triples that to six in three more. Five presses in all, which is two and three added together.
Example 2
- Input
- n = 2
- Output
- 2
Copy the single mark, then paste it once.
Example 3
- Input
- n = 9
- Output
- 6
Three presses reach three marks, and three more triple that to nine.
Constraints
- 1 <= n <= 1000
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
Python
def min_steps(n: int) -> int:Java
public int minSteps(int n)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's