Home » Interview coding problems/challenges

# 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

*at moment 3.*

**key3**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

Comments and Discussions!