2 Keys Keyboard - Practice Coding Problems

2 Keys Keyboard - Problem

There is only one character 'A' on the screen of a notepad. You can perform one of two operations on this notepad for each step:

Copy All: You can copy all the characters present on the screen (a partial copy is not allowed).
Paste: You can paste the characters which are copied last time.

Given an integer n, return the minimum number of operations to get the character 'A' exactly n times on the screen.

Input & Output

Example 1 — Basic Case

$ Input: n = 3

› Output: 3

💡 Note: Initially we have 1 'A'. Copy All (1 op) → clipboard has 'A', screen has 'A'. Paste (1 op) → screen has 'AA'. Paste (1 op) → screen has 'AAA'. Total: 3 operations.

Example 2 — Composite Number

$ Input: n = 9

› Output: 6

💡 Note: Optimal path: Copy 1A → Paste to get 3A (3 ops), then Copy 3A → Paste to get 6A → Paste to get 9A (3 more ops). Total: 6 operations. This equals 3+3 (prime factors of 9 = 3²).

Example 3 — Prime Number

$ Input: n = 7

› Output: 7

💡 Note: Since 7 is prime, we can only paste one by one: Copy 1A, then paste 6 times to get 7A. Total: 7 operations.

Constraints

1 ≤ n ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Initial State

Start with 1 'A' on screen

Copy-Paste Strategy

Choose optimal sequence of copy and paste operations

Target Reached

Achieve exactly n 'A's with minimum operations

Key Takeaway

🎯 Key Insight: The minimum operations equals the sum of all prime factors of n

Asked in

G Google 35 M Microsoft 28 A Amazon 22

The key insight is that this problem is equivalent to prime factorization. The minimum operations needed equals the sum of all prime factors of n (including duplicates). Best approach uses prime factorization in O(√n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Prime Factorization (Optimal)	O(√n)	O(1)	The minimum operations equals the sum of all prime factors of n
1D Dynamic Programming	O(n²)	O(n)	Use bottom-up DP where dp[i] represents minimum operations to get i characters
Brute Force Recursion	O(2^n)	O(n)	Try all possible sequences of copy and paste operations recursively
Memoization (Top-Down DP)	O(n²)	O(n²)	Use memoization to cache results of subproblems and avoid redundant calculations

Prime Factorization (Optimal) — Algorithm Steps

Find all prime factors of n
Sum up all prime factors (including duplicates)
This sum equals minimum operations needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Factorize n

Find all prime factors of the target number

Sum Factors

Add up all prime factors including duplicates

Result

This sum equals minimum copy-paste operations

Code -

solution.c — C

#include <stdio.h>

int solution(int n) {
    if (n == 1) return 0;
    
    int result = 0;
    int factor = 2;
    
    while (factor * factor <= n) {
        while (n % factor == 0) {
            result += factor;
            n /= factor;
        }
        factor++;
    }
    
    // If n > 1, then it's a prime factor
    if (n > 1) {
        result += n;
    }
    
    return result;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(√n)

We only need to check divisors up to square root of n

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables, no extra data structures

✓ Linear Space

78.5K Views

Medium Frequency

~25 min Avg. Time

1.8K 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

Prime Factorization (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler