Four-Key Letter Printer

Medium

A keyboard has only four keys: - **Letter** types one letter x at the end of the text; - **Select** selects all the text on the screen; - **Copy** puts the selection into the clipboard; - **Paste** appends the clipboard contents to the end of the text. The screen and the clipboard start empty. Given presses, the number of key presses you have, return the largest number of letters that can be on the screen after at most presses presses.

Example 1

presses=5 → 5

Typing five letters is best: select, copy and paste would not gain anything within so few presses.

Example 2

presses=8 → 12

Letter, letter, letter, select, copy, paste, paste, paste: 3 + 3 · 3 = 12 letters.

Example 3

presses=1 → 1

Constraints

1 ≤ presses ≤ 50

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

presses=5

Expected

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