# Special Keyboard

Special Keyboard: In this article we are going to see an interview problem that is special keyboard problem and its solution – which has been featured in Amazon interview rounds.
Submitted by Radib Kar, on June 09, 2020

Problem statement:

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
```

Solution Approach:

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
```

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates