Home » Technical Interview Questions » Dynamic Programming Interview Questions » How to print maximum number of A’s using given four keys

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


Reading Time - 4 mins


Difficulty Level Easy

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:

  1. Key1 – Prints ‘A’ on screen
  2. Key2 – Select the whole screen.
  3. Key3 – Copy the selected content.
  4. 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.

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

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.

READ  Distinct Subsequences

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;
}
18
192

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);
    }
}
18
192

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).

READ  Decode Ways

Space Complexity: O(1)

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

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions