## 651. 4 Keys Keyboard

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 = 3
Output: 3
Explanation:
We can at most get 3 A's on screen by pressing following key sequence:
A, A, A


Example 2:

Input: N = 7
Output: 9
Explanation:
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. 1 <= N <= 50
2. Answers will be in the range of 32-bit signed integer.

b'
\n\n
\n

#### Approach Framework

\n

Explanation

\n

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
\n

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

\n
\n

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

\n

Intuition and Algorithm

\n

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.

\n

Taking the best of these candidates lets us find best[k] in terms of previous best[j], j < k.

\n\n

Complexity Analysis

\n
\n
• \n

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

\n
• \n
• \n

Space Complexity: , the size of best.

\n
• \n
\n
\n

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

\n

Intuition

\n

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.

\n

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.

\n

Thus, we never multiply by more than 5.

\n

Algorithm

\n

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.

\n

Complexity Analysis

\n
\n
• \n

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

\n
• \n
• \n

Space Complexity: , the size of best.

\n
• \n
\n
\n

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

\n

Explanation

\n

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

\n

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.

\n

Now, we need to make a few more deductions.

\n
\n
• \n

We never add after multiplying: if we add c after multiplying by k, we should instead multiply by k+c.

\n
• \n
• \n

We never add after 5: If we add 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
• \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
\n

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

\n

We 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.

\n\n

Complexity Analysis

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

Analysis written by: @awice.

\n
'