Print maximum number of ‘A’ using given four keys
Imagine you have a special keyboard with the following keys:
- Key 1: Prints ‘A’ on screen
- Key 2: (ctrl-A): Select 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.
If you can only press the keyboard for N times (with the above four keys), write a program to produce maximum numbers of A’s. That is to say, the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce).
Examples:
Input: N = 3
Output: 3
Explanation: We can at most get 3 A’s on screen by pressing following key sequence. A, A, AInput: N = 7
Output: 9
Explanation: We can at most get 9 A’s on screen by pressing following key sequence. A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl VInput: N = 11
Output: 27
Explanation: We can at most get 27 A’s on screen by pressing following key sequence. A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V, Ctrl A, Ctrl C, Ctrl V, Ctrl V
Approach:
Below are few important points to note.
- For N < 7, the output is N itself.
- Ctrl V can be used multiple times to print current buffer (See last two examples above). The idea to compute the optimal string length for N keystrokes by using a simple insight. The sequence of N keystrokes which produces an optimal string length will end with a suffix of Ctrl-A, a Ctrl-C, followed by only Ctrl-V’s (For N > 6).
The task is to find out the breakpoint after which we get the above suffix of keystrokes. Definition of a breakpoint is that instance after which we need to only press Ctrl-A, Ctrl-C once and the only Ctrl-V’s afterwards to generate the optimal length. If we loop from N-3 to 1 and choose each of these values for the break-point, and compute that optimal string they would produce. Once the loop ends, we will have the maximum of the optimal lengths for various breakpoints, thereby giving us the optimal length for N keystrokes.
Below are the implementation of the above approach:
#include <iostream>
using namespace std;
// A recursive function that returns the optimal length
// string for N keystrokes
int findOptimal(int N)
{
// The optimal string length is N when N is smaller
// than 7
if (N <= 6)
return N;
// Initialize result
int max = 0;
// TRY ALL POSSIBLE BREAK-POINTS
// For any keystroke N, we need to loop from N-3
// keystrokes back to 1 keystroke to find a
// breakpoint 'b' after which we will have Ctrl-A,
// Ctrl-C and then only Ctrl-V all the way.
for (int b = N - 3; b >= 1; b--) {
// If the breakpoint is at b'th keystroke then
// the optimal string would have length
// (N-b-1)*findOptimal(b);
int curr = (N - b - 1) * findOptimal(b);
if (curr > max)
max = curr;
}
return max;
}
// Driver program
int main()
{
// Loop from 1 to 20 keystrokes to find the maximum
// number of A's
for (int N = 1; N <= 20; N++) {
cout << "Maximum Number of A's with " << N
<< " keystrokes is " << findOptimal(N) << endl;
}
return 0;
}
// This code is contributed by Shivam Gupta
/* A recursive C program to print maximum number of A's
using following four keys */
#include <stdio.h>
// A recursive function that returns the optimal length
// string for N keystrokes
int findoptimal(int N)
{
// The optimal string length is N when N is smaller than
// 7
if (N <= 6)
return N;
// Initialize result
int max = 0;
// TRY ALL POSSIBLE BREAK-POINTS
// For any keystroke N, we need to loop from N-3
// keystrokes back to 1 keystroke to find a breakpoint
// 'b' after which we will have Ctrl-A, Ctrl-C and then
// only Ctrl-V all the way.
int b;
for (b = N - 3; b >= 1; b--) {
// If the breakpoint is s at b'th keystroke then
// the optimal string would have length
// (n-b-1)*screen[b-1];
int curr = (N - b - 1) * findoptimal(b);
if (curr > max)
max = curr;
}
return max;
}
// Driver program
int main()
{
int N;
// for the rest of the array we will rely on the
// previous entries to compute new ones
for (N = 1; N <= 20; N++)
printf("Maximum Number of A's with %d keystrokes "
"is %d\n",
N, findoptimal(N));
}
public class MaximumAs {
// A recursive function that returns the optimal length
// string for N keystrokes
static int findOptimal(int N)
{
// The optimal string length is N when N is smaller
// than 7
if (N <= 6)
return N;
// Initialize result
int max = 0;
// TRY ALL POSSIBLE BREAK-POINTS
// For any keystroke N, we need to loop from N-3
// keystrokes back to 1 keystroke to find a
// breakpoint 'b' after which we will have Ctrl-A,
// Ctrl-C and then only Ctrl-V all the way.
for (int b = N - 3; b >= 1; b--) {
// If the breakpoint is at b'th keystroke then
// the optimal string would have length
// (N-b-1)*findOptimal(b);
int curr = (N - b - 1) * findOptimal(b);
if (curr > max)
max = curr;
}
return max;
}
// Driver program
public static void main(String[] args)
{
// Loop from 1 to 20 keystrokes to find the maximum
// number of A's
for (int N = 1; N <= 20; N++) {
System.out.println("Maximum Number of A's with "
+ N + " keystrokes is "
+ findOptimal(N));
}
}
}
// This code is contributed by Shivam
class MaximumAs {
// A memoization map to store results of subproblems
static memo = new Map();
// A recursive function that returns the optimal length string for N keystrokes
static findOptimal(N) {
// Check if the result for N keystrokes is already computed
if (this.memo.has(N)) {
return this.memo.get(N);
}
// The optimal string length is N when N is smaller than 7
if (N <= 6) {
return N;
}
// Initialize result
let max = 0;
// TRY ALL POSSIBLE BREAK-POINTS
// For any keystroke N, we need to loop from N-3 keystrokes back to 1 keystroke
// to find a breakpoint 'b' after which we will have Ctrl-A, Ctrl-C and then
// only Ctrl-V all the way.
for (let b = N - 3; b >= 1; b--) {
// If the breakpoint is at b'th keystroke then the optimal string would
// have length
// (N - b - 1) * findOptimal(b);
let curr = (N - b - 1) * MaximumAs.findOptimal(b);
if (curr > max) {
max = curr;
}
}
// Store the result in memoization map
this.memo.set(N, max);
return max;
}
}
// Driver program
function main() {
// Loop from 1 to 20 keystrokes to find the maximum number of A's
for (let N = 1; N <= 20; N++) {
console.log(`Maximum Number of A's with ${N} keystrokes is ${MaximumAs.findOptimal(N)}`);
}
}
main();
// This code is contributed by Shivam
Output
Maximum Number of A's with 1 keystrokes is 1 Maximum Number of A's with 2 keystrokes is 2 Maximum Number of A's with 3 keystrokes is 3 Maximum Number of A's with 4 keystrokes is 4 Maximum Number of A'...
Approach (Dynamic Programming): The above function computes the same subproblems again and again. Recomputations of same subproblems can be avoided by storing the solutions to subproblems and solving problems in bottom up manner. where screen[n-1] is used to store result for N = n.
Below are the implementation of the above approach:
#include<stdio.h>
// this function returns the optimal length string for N keystrokes
int findoptimal(int N)
{
// The optimal string length is N when N is smaller than 7
if (N <= 6)
return N;
// An array to store result of subproblems
int screen[N];
int b; // To pick a breakpoint
// Initializing the optimal lengths array for uptil 6 input
// strokes.
int n;
for (n=1; n<=6; n++)
screen[n-1] = n;
// Solve all subproblems in bottom manner
for (n=7; n<=N; n++)
{
// Initialize length of optimal string for n keystrokes
screen[n-1] = 0;
// For any keystroke n, we need to loop from n-3 keystrokes
// back to 1 keystroke to find a breakpoint 'b' after which we
// will have ctrl-a, ctrl-c and then only ctrl-v all the way.
for (b=n-3; b>=1; b--)
{
// if the breakpoint is at b'th keystroke then
// the optimal string would have length
// (n-b-1)*screen[b-1];
int curr = (n-b-1)*screen[b-1];
if (curr > screen[n-1])
screen[n-1] = curr;
}
}
return screen[N-1];
}
// Driver program
int main()
{
int N;
// for the rest of the array we will rely on the previous
// entries to compute new ones
for (N=1; N<=20; N++)
printf("Maximum Number of A's with %d keystrokes is %d\n",
N, findoptimal(N));
}
public class OptimalStringLength {
// This function returns the optimal length string for N
// keystrokes
public static int findOptimal(int N)
{
// The optimal string length is N when N is smaller
// than 7
if (N <= 6) {
return N;
}
// An array to store result of subproblems
int[] screen = new int[N];
int b; // To pick a breakpoint
// Initializing the optimal lengths array for up to
// 6 input strokes.
for (int n = 1; n <= 6; n++) {
screen[n - 1] = n;
}
// Solve all subproblems in bottom manner
for (int n = 7; n <= N; n++) {
// Initialize length of optimal string for n
// keystrokes
screen[n - 1] = 0;
// For any keystroke n, we need to loop from n-3
// keystrokes back to 1 keystroke to find a
// breakpoint 'b' after which we will have
// ctrl-a, ctrl-c and then only ctrl-v all the
// way.
for (b = n - 3; b >= 1; b--) {
// if the breakpoint is at b'th keystroke
// then the optimal string would have length
// (n - b - 1) * screen[b - 1];
int curr = (n - b - 1) * screen[b - 1];
if (curr > screen[n - 1]) {
screen[n - 1] = curr;
}
}
}
return screen[N - 1];
}
// Driver program
public static void main(String[] args)
{
int N;
// For the rest of the array, we will rely on the
// previous entries to compute new ones
for (N = 1; N <= 20; N++) {
System.out.println("Maximum Number of A's with "
+ N + " keystrokes is "
+ findOptimal(N));
}
}
}
// This code is contributed by Ayush Mishra
# Importing the sys module to set recursion limit
import sys
sys.setrecursionlimit(10000)
# This function returns the optimal length string for N keystrokes
def find_optimal(N):
# The optimal string length is N when N is smaller than 7
if N <= 6:
return N
# An array to store the result of subproblems
screen = [-1] * N
# Initializing the optimal lengths array for up to 6 input strokes
for n in range(1, 7):
screen[n - 1] = n
# Solve all subproblems in a bottom-up manner
for n in range(7, N + 1):
# Initialize the length of the optimal string for n keystrokes
screen[n - 1] = 0
# For any keystroke n, we need to loop from n-3 keystrokes
# back to 1 keystroke to find a breakpoint 'b' after which we
# will have ctrl-a, ctrl-c, and then only ctrl-v all the way
for b in range(n - 3, 0, -1):
# If the breakpoint is at the b'th keystroke then
# the optimal string would have length (n-b-1) * screen[b-1]
curr = (n - b - 1) * screen[b - 1]
if curr > screen[n - 1]:
screen[n - 1] = curr
return screen[N - 1]
# Driver program
if __name__ == "__main__":
# For the rest of the array, we will rely on the previous
# entries to compute new ones
for N in range(1, 21):
print(f"Maximum Number of A's with {N} keystrokes is {find_optimal(N)}")
Output
Maximum Number of A's with 1 keystrokes is 1 Maximum Number of A's with 2 keystrokes is 2 Maximum Number of A's with 3 keystrokes is 3 Maximum Number of A's with 4 keystrokes is 4 Maximum Number of A'...