Four Keys Keyboard

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

Approach: In the previous approach you can observe that we are doing repeated calculations. We store or memoize the result of already computed subproblems to avoid repetition. This can be done as follows.

 

Algorithm:

1. This is a recursive approach.
2. Make an array of integers ‘MEMO’ of size ‘N’ to store already computed results. Fill this array by -1.
3. Call a recursive function to find the answer, Let name this recursive function ‘HELPER(N)’. In each recursive call to this function do following -:
   • If ‘N’ is smaller than 7, return ‘N’.
   • If ‘MEMO[N]’ != -1, i.e this subproblem is already computed, then return ‘MEMO[N]’.
   • Otherwise, Initialize an integer variable ‘RESULT’: = 0.
   • 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 by calling ‘HELPER(N - i - 2)’ and update ‘RESULT’ with a maximum of its current value and product of value returned by a recursive call with (i + 1).
   • Assign 'MEMO[N]' = ‘RESULT’
   • Return ‘MEMO[N]’.

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.

We can implement this recurrence relation using dynamic programming as follows.

 

Algorithm:

1. If ‘N’ is smaller than 7, return ‘N’.
2. Create an integer array ‘DP’ of size ‘N’, where ‘DP[i]’ gives the maximum number of ‘A’s that can be printed by ‘i’ keystrokes. Note, we are assuming 1 based indexing.
3. Run a loop where ‘i’ ranges from 1 to 6 and for each ‘i’ assign DP[i] = i.
4. Run a loop where ‘i’ ranges from 7 to n and for each ‘i’ do the following.
   • Run a loop where ‘j’ ranges from 1 to i - 3 and for each ‘j’ assign DP[i]:= max(DP[i], (i + 1) * DP[i - j - 2]).
5. Return DP[n].

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 at most  Ctrl-V’s.

 

We can also observe that as the number of A’s become large, the effect of pressing Ctrl-V more than 3 times starts to become the same as compared to just pressing Ctrl-A, Ctrl-C and Ctrl-V again. So, the above code can be made more efficient by checking the effect of pressing Ctrl-V for 1, 2, and 3 times only.

 

So, if F(n) gives the maximum number of ‘A’s that can be printed by ‘n’ keystrokes and ‘x’ represents 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 3.

We can implement this recurrence relation using dynamic programming as follows.

 

Algorithm:

1. If ‘N’ is smaller than 7, return 'N’.
2. Create an integer array ‘DP’ of size ‘N’, where ‘DP[i]’ gives the maximum number of ‘A’s that can be printed by ‘i’ keystrokes. Note, we are assuming 1 based indexing.
3. Run a loop where ‘i’ ranges from 1 to 6 and for each ‘i’ assign DP[i]:= i.
4. Run a loop where ‘i’ ranges from 7 to 'N' and for each ‘i’ do the following.
   • Run a loop where ‘j’ ranges from 1 to 3 and for each ‘j’ assign DP[i]:= max(DP[i], (i + 1) * DP[i - j - 2]).
5. Return ‘DP[n]’.