Four Keys Keyboard

Posted: 13 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Imagine you have a special keyboard with the following four 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.

Given a positive integer ‘N’, find out the maximum numbers of ‘A’s you can print on the screen if you are allowed to press the keys of this special keyboard ‘N’ times.

Input Format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines represent the ‘T’ test cases.

The first and only line of each test case contains a positive integer ‘N’, representing the number of times you can press the keys of the keyboard.
Output Format:
For each test case, print in a separate line, the maximum number of ‘A’s that you can print on the screen.
Follow-up:
Try solving the problem in O(N) complexity.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N <= 150

Where ‘T’ is the number of test cases and  ‘N’ is the integer representing the number of times you can press the keys of the keyboard.


Time Limit: 1 sec
Approach 1

Approach: We can observe that if  ‘n’ < 7, the output is ‘n’ itself. Otherwise, if ‘n’ is greater than or equal to 7, then the optimal sequence of operations will end with a suffix of one Ctrl-A, one Ctrl-C, followed by one or several Ctrl-V’s.

 

If F(n) given the maximum number of ‘A’s that can be printed by ‘n’ keystrokes and ‘x’ represent the number of Ctrl-V’s at the end, then recurrence relation should be-:

F(n) = n if n < 7;

F(n) = maximum of all  (x+1)*F(n-x-2),  where ‘x’ ranges from 1 to n-3. Here, we try for all possible points from where the suffix may start.

 

This approach's algorithm can be implemented as follows.

 

  1. This is a recursive approach.
  2. If ‘N’ is smaller than 7, return ‘N’.
  3. Otherwise, Initialize an integer variable ‘RESULT’: = 0.
  4. Run a loop where ‘i’ ranges from 1 to ‘N’ - 3. And for each ‘i’ recursively find the maximum number of ‘A’s that can be printed in ‘N - i - 2’  keystrokes and update ‘RESULT’ with a maximum of its current value and product of value returned by a recursive call with (i + 1).
  5. Return ‘RESULT’.
Try Problem