4 Keys Keyboard - Practice Coding Problems

4 Keys Keyboard - Problem

Imagine you have a special keyboard with the following keys:

A: Print one 'A' on the screen
Ctrl-A: Select the whole screen
Ctrl-C: Copy selection to buffer
Ctrl-V: Print buffer on screen appending it after what has already been printed

Given an integer n, return the maximum number of 'A' you can print on the screen with at most n presses on the keys.

Input & Output

Example 1 — Small Input

$ Input: n = 7

› Output: 9

💡 Note: Best sequence: A-A-A-Ctrl+A-Ctrl+C-Ctrl+V-Ctrl+V (3 A's × 3 = 9 A's total)

Example 2 — Very Small Input

$ Input: n = 3

› Output: 3

💡 Note: Just press A three times: A-A-A gives 3 A's

Example 3 — Larger Input

$ Input: n = 9

› Output: 12

💡 Note: Optimal sequence uses copy-paste: A-A-A-A-Ctrl+A-Ctrl+C-Ctrl+V-Ctrl+V-Ctrl+V (4 A's × 3 = 12 A's total)

Constraints

1 ≤ n ≤ 50
All key presses must be valid keyboard operations

Visualization

Tap to expand

Understanding the Visualization

Input

n=7 key presses allowed

Strategy

Choose between pressing A or copy-paste sequences

Output

Maximum 9 A's achievable

Key Takeaway

🎯 Key Insight: The optimal strategy balances between typing A's initially and using copy-paste sequences to multiply them efficiently

Asked in

G Google 45 M Microsoft 30 a Amazon 25

The key insight is that after typing some A's, the optimal strategy is Ctrl+A, Ctrl+C, then multiple Ctrl+V operations. We use dynamic programming to find the optimal number of A's to type before starting copy-paste sequences. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Bottom-Up Dynamic Programming	O(n²)	O(n)	Build solution iteratively using 1D DP array
Memoization (Top-Down DP)	O(n²)	O(n²)	Cache recursive results to avoid recomputation
Try All Possible Sequences	O(n²)	O(n)	Recursively try all possible key press combinations

Bottom-Up Dynamic Programming — Algorithm Steps

Step 1: Initialize DP array with base cases (dp[i] = i for small i)
Step 2: For each position, try pressing 'A' or copy-paste sequences
Step 3: Take maximum of all possibilities

Visualization

Tap to expand

Step-by-Step Walkthrough

Base Cases

dp[1]=1, dp[2]=2, dp[3]=3 (just press A)

Fill Table

For each i, consider pressing A or copy-paste sequences

Optimal Choice

Take maximum of all possibilities

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int solution(int n) {
    if (n <= 3) {
        return n;
    }
    
    // dp[i] = maximum A's with i key presses
    int* dp = (int*)calloc(n + 1, sizeof(int));
    
    // Base cases
    for (int i = 1; i <= 3 && i <= n; i++) {
        dp[i] = i;
    }
    
    // Fill DP table
    for (int i = 4; i <= n; i++) {
        // Option 1: Press A
        dp[i] = dp[i - 1] + 1;
        
        // Option 2: Copy-paste sequences
        for (int j = 1; j < i - 2; j++) {
            if (i - 2 - j > 0) {
                int candidate = dp[i - 2 - j] * (j + 1);
                if (candidate > dp[i]) {
                    dp[i] = candidate;
                }
            }
        }
    }
    
    int result = dp[n];
    free(dp);
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n positions, we try O(n) different copy-paste sequences

⚠ Quadratic Growth

Space Complexity

O(n)

DP array of size n to store maximum A's for each key press count

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bottom-Up Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler