How to print maximum number of A’s using given four keys

Table of Contents

Problem Statement

How to print maximum number of A’s using given four keys, this problem states that you have the option to choose which key to press. The keys perform the following tasks:

Key1 – Prints ‘A’ on screen
Key2 – Select the whole screen.
Key3 – Copy the selected content.
Key4 – Print the copied content.

You can press keys only for N times, find out the maximum number of A’s that can be printed. By using any of the combinations you can make, find the maximum number of A’s that can be printed.

Example

Number of keys that can be pressed = 2

Number of A's that can be printed = 2

Explanation: Since any other combination won’t be able to find any better result. Using any other combination of key presses, won’t be able to print more number of A’s. We can try any other combination. Let’s say we print a single A. Because if we don’t print ‘A’, we can’t select ‘A’ and then print it. So, it is better to print a single ‘A’. Afterward, we may perform any of the three combinations, selection, printing, and copying. But any of these combinations won’t be able to provide any better results.

Number of keys that can be pressed = 6

Number of A's that can be printed = 6

Explanation: We will use the following 6 keypresses, Key1(prints ‘A’), Key1, Key1, Key2(Selects the whole screen content), Key3(Copy the selected content), Key4(Prints the copied content). There may be other keypresses which may print the same number of A’s.

Approach

Finding how to print maximum number of A’s using given four keys, can be solved if we start from the number of keypresses = N-3 to 1 and try to find out the maximum number of A’s.
We will consider that the ith position is the point from where we press Key2, Key3, and then a sequence of Key4. Now, if we loop from N-3 to 1. There may be many such points.

As always, we need a base case because the problem uses dynamic programming. Here the case is if n <=6 we simply print the number. Why do we call this dynamic programming even though in the code we don’t use any DP array? Because the problem satisfies the two conditions: overlapping subproblems and optimal substructure. Each problem can be further subdivided which is then further divided.

Code

C++ code to find maximum number of As that can be printed

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

int maximumNumberOfAsPrinted(int numberOfKeyPresses)
{
  if(numberOfKeyPresses <= 6)
    return numberOfKeyPresses;

  int maxNumberOfAs = 0;
  for(int i = numberOfKeyPresses-3; i>=1;i--) {
    // here we consider that after ith keystroke we are performing only selection, copy once and then paste
    // thus starting from numberOfKeyPresses-3
    int numberOfAs = (numberOfKeyPresses-i-1)*maximumNumberOfAsPrinted(i);
    if (numberOfAs > maxNumberOfAs)
      maxNumberOfAs = numberOfAs;
  }
  return maxNumberOfAs;
}

int main()
{
  int numberOfKeyPresses;cin>>numberOfKeyPresses;
  int numberOfAsPrinted = maximumNumberOfAsPrinted(numberOfKeyPresses);
  cout<<numberOfAsPrinted;
}

Java code to find maximum number of As that can be printed

import java.util.*;

class Main{
    static int maximumNumberOfAsPrinted(int numberOfKeyPresses)
    {
    	if(numberOfKeyPresses <= 6)
    		return numberOfKeyPresses;
    
    	int maxNumberOfAs = 0;
    	for(int i = numberOfKeyPresses-3; i>=1;i--) {
    		// here we consider that after ith keystroke we are performing only selection, copy once and then paste
    		// thus starting from numberOfKeyPresses-3
    		int numberOfAs = (numberOfKeyPresses-i-1)*maximumNumberOfAsPrinted(i);
    		if (numberOfAs > maxNumberOfAs)
    			maxNumberOfAs = numberOfAs;
    	}
    	return maxNumberOfAs;
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
    	int numberOfKeyPresses = sc.nextInt();
    	int numberOfAsPrinted = maximumNumberOfAsPrinted(numberOfKeyPresses);
    	System.out.println(numberOfAsPrinted);
    }
}

Complexity Analysis

Time Complexity: O(N)

Since we simply ran a loop over a number of keypresses. The algorithm has a linear time complexity of O(N).

Space Complexity: O(1)

Since we are storing just some particular integers, and elements. We have constant space complexity.