Medium

Quiz

#650 2 Keys Keyboard

APPROACH

A notepad starts with a single 'A'. Each step you may either Copy All (copy everything on screen) or Paste (paste the last copied content). Given an integer n, return the fewest total operations needed to produce exactly n copies of 'A' on screen.

Example 1:

Input: n = 3

Output: 3

Explanation: Initially, we have one character 'A'.

In step 1, we use Copy All operation.

In step 2, we use Paste operation to get 'AA'.

In step 3, we use Paste operation to get 'AAA'.

Example 2:

Input: n = 1

Output: 0

1 of 4

1:00

What is the optimal approach for this problem?