This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Imagine you have a special keyboard with the following keys:

`Key 1: (A)`

: Print one 'A' on screen.

`Key 2: (Ctrl-A)`

: Select the whole screen.

`Key 3: (Ctrl-C)`

: Copy selection to buffer.

`Key 4: (Ctrl-V)`

: Print buffer on screen appending it after what has already been printed.

Now, you can only press the keyboard for **N** times (with the above four keys), find out the maximum numbers of 'A' you can print on screen.

**Example 1:**

Input:N = 3Output:3Explanation:We can at most get 3 A's on screen by pressing following key sequence: A, A, A

**Example 2:**

Input:N = 7Output:9Explanation:We can at most get 9 A's on screen by pressing following key sequence: A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

**Note:**

- 1 <= N <= 50
- Answers will be in the range of 32-bit signed integer.

b'

\n

\n#### Approach Framework

\n

\n#### Approach #1: Dynamic Programming [Accepted]

\n

\n#### Approach #2: Optimized Dynamic Programming [Accepted]

\n

\n#### Approach #3: Mathematical [Accepted]

\n

\n

'
\n\n

\n\n

**Explanation**

We either press \'A\', or press \'CTRL+A\', \'CTRL+C\', and some number of \'CTRL+V\'s. Thus, there are only two types of moves:

\n- \n
- Add (Cost
`1`

): Add`1`

\n - Multiply (Cost
`k+1`

): Multiply by`k`

, where`k >= 2`

. \n

In the following explanations, we will reference these as moves.

\n\n

**Intuition and Algorithm**

Say `best[k]`

is the most number of `\'A\'`

\'s possible after `k`

moves. If the last move was adding, then `best[k] = best[k-1] + 1`

. If the last move was multiplying, then `best[k-(x+1)] = best[k-(x+1)] * x`

for some `x < k-1`

.

Taking the best of these candidates lets us find `best[k]`

in terms of previous `best[j], j < k`

.

**Complexity Analysis**

- \n
- \n
Time Complexity: . We have two nested for-loops, each of which do work.

\n \n - \n
Space Complexity: , the size of

\n`best`

. \n

\n

**Intuition**

If we multiply by `2N`

, paying a cost of `2N+1`

, we could instead multiply by `N`

then `2`

, paying `N+4`

. When `N >= 3`

, we don\'t pay more by doing it the second way.

Similarly, if we are to multiply by `2N+1`

paying `2N+2`

, we could instead multiply by `N+1`

then `2`

, paying `N+5`

. Again, when `N >= 3`

, we don\'t pay more doing it the second way.

Thus, we never multiply by more than `5`

.

**Algorithm**

Our approach is the same as *Approach #1*, except we do not consider `k-x-1 > 5`

in our inner loop. For brevity, we have omitted this solution.

**Complexity Analysis**

- \n
- \n
Time Complexity: . We have two nested for-loops, but the inner loop does work.

\n \n - \n
Space Complexity: , the size of

\n`best`

. \n

\n

**Explanation**

As in *Approach #2*, we never multiply by more than 5.

When `N`

is arbitrarily large, the long run behavior of multiplying by `k`

repeatedly is to get to the value . Analyzing the function at values , it attains a peak at . Thus, we should expect that *eventually*, `best[K] = best[K-5] * 4`

.

Now, we need to make a few more deductions.

\n- \n
- \n
We never add after multiplying: if we add

\n`c`

after multiplying by`k`

, we should instead multiply by`k+c`

. \n - \n
We never add after 5: If we add

\n`1`

then multiply by`k`

to get to`(x+1) * k = xk + k`

, we could instead multiply by`k+1`

to get to`xk + x`

. Since`k <= 5`

, we must have`x <= 5`

for our additions to not be dominated. \n - \n
The number of multiplications by 2, 3, or 5 is bounded.

\n \n - \n
Every time we\'ve multiplied by 2 two times, we prefer to multiply by 4 once for less cost. (4^1 for a cost of 5, vs 2^2 for a cost of 6.)

\n \n - Every time we\'ve multiplied by 3 five times, we prefer to multiply by 4 four times for the same cost but a larger result. (4^4 > 3^5, and cost is 20.) \n
- Every time we\'ve multiplied by 5 five times, we prefer to multiply by 4 six times for the same cost but a larger result. (4^6 > 5^5, and cost is 30.) \n

Together, this shows there are at most 5 additions and 9 multiplications by a number that isn\'t 4.

\nWe can find the first 14 operations on 1 by hand: `1, 2, 3, 4, 5, 6, 9, 12, 16, 20, 27, 36, 48, 64, 81`

. After that, every subsequent number is achieved by multiplying by 4: ie., `best[K] = best[K-5] * 4`

.

**Complexity Analysis**

- \n
- Time and Space Complexity: . \n

\n

Analysis written by: @awice.

\n