Copy and Paste Letters

Medium

A blank text editor contains a single letter x. You cannot type anything else; only two actions are available: - **Copy**: copy the entire text on the screen to the clipboard (partial copies are not allowed); - **Paste**: append whatever the clipboard held after the last copy. The clipboard starts empty. Each action takes one step. Given an integer goal, return the minimum number of actions needed to have exactly goal letters on the screen.

Example 1

goal=4 → 4

Copy (clipboard: 1), paste (2 letters), copy (clipboard: 2), paste (4 letters): four actions.

Example 2

goal=9 → 6

Copy and paste twice to get three letters, then copy and paste twice again to get nine: six actions in total.

Example 3

goal=1 → 0

The single letter is already on screen, so nothing needs to be done.

Constraints

1 ≤ goal ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math Dynamic Programming

Similar problems

Counting Grid Routes Medium Counting Search Tree Shapes Medium Every Bracketing Result Medium Numbers Made of Twos, Threes and Fives Medium Fewest Square Terms Medium

Input

goal=4

Expected

Run checks the first 3 tests in your browser. Submit checks all 66 tests on the server, hidden ones included.