Q:

Imagine you have a special keyboard with four types of keys: Key 1: Prints \'I\' on screen Key 2: Select whatever printed in screen Key 3: Copy selection to buffer Key 4: Append buffer on-screen after what has already been printed

mahmoud2506
Save to bookmark
|
2022-05-01
|
  243 
0

Special Keyboard

Imagine you have a special keyboard with four types of keys:

Key 1: Prints 'I' on screen

Key 2: Select whatever printed in screen

Key 3: Copy selection to buffer

Key 4: Append buffer on-screen after what has already been printed. If you can only press the keyboard for N times (with the above four keys), write a program to produce maximum numbers of I's possible to be printed on the screen.

Input:

Input is N, number of times keys can be pressed in total.

Output:

Print maximum number of I's possible to print

Constraints:

1 ≤ N ≤ 75

Example:

Input:
2

Output:
2

Explanation:
We can at most get 2 I's on screen by pressing 
following key sequence Key1, key1.
Pressing other keys have no effect. 
Like key 1, key2 will produce only one I on screen. 

Input:
7

Output:
9

Explanation:
We can at most get 9 I's on screen by pressing 
following key sequence.
Key1, Key1, Key1, Key2, Key3, key4, Key4

I //after pressing key1
I I  //again pressing key 1
I I I //again pressing key1
 
I I I //pressing key2 selects three I's
I I I // pressing key3 copies these three I's to buffer
I I I I I I // pressing key4 appends these three I's 
I I I I I I I I I // pressing key4 again appends these three I's
C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-01
need an explanation for this answer? contact us directly to get an explanation for this answer

Basically,

Two things need to be understood to solve this problem

Key4 appends whatever is printed already on screen before 3 key pressing

That means at moment 4,

You can append whatever was printed while moment 1 as to print in moment 4, you need to press key2 at moment 2 and key3 at moment 3.

So, the recursive function can be written as

Let,

F(n) = max number of I’s printed on screen

So, for n>3

F(n) = max(f(j)*(n-j-1)) for 1<=j<=n-3

Where, 
F(j) = already printed characters up to moment j 
and (n-j-1) is number of appending possible

So, now we need to convert the recursion into DP.

1)  Initialize dp[n+1] like following base value;
2)  for i=0 to n
        dp[i]=i;
3)  Fill the DP table
        for i=4 to n
            for j=i-3 to 1,j--
                dp[i]=max(dp[i],dp[j]*(i-j-1));
            end for
        End for
4)  Return dp[n]

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

int specialKeyboard(int n)
{

    int dp[n + 1];
    for (int i = 0; i <= n; i++)
        dp[i] = i;

    for (int i = 6; i <= n; i++) {
        for (int j = i - 3; j >= 1; j--) {
            dp[i] = std::max(dp[i], dp[j] * (i - j - 1));
        }
    }

    return dp[n];
}

int main()
{
    int t, n, item;

    cout << "Input n, number of times keys to be pressed: ";
    scanf("%d", &n);
    
    cout << "max no of i's got printed: " << specialKeyboard(n) << endl;

    return 0;
}

Output:

Input n, number of times keys to be pressed: 7
max no of i's got printed: 9

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

interview C++ coding problems/challenges | Recursion
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Given a string S, write a program to check if it i... >>
<< Shivang is very foodie but he has a diet plan. He ...