2 Keys Keyboard
Problem
Start with 1 'A'. Two ops: copy-all and paste. Minimum ops to print exactly n 'A's.
n = 96def min_steps(n):
out = 0; d = 2
while n > 1:
while n % d == 0: out += d; n //= d
d += 1
return outfunction minSteps(n) {
let out = 0;
for (let d = 2; n > 1; d++) while (n % d === 0) { out += d; n = n / d; }
return out;
}int minSteps(int n) {
int out = 0;
for (int d = 2; n > 1; d++) while (n % d == 0) { out += d; n /= d; }
return out;
}int minSteps(int n) {
int out = 0;
for (int d = 2; n > 1; d++) while (n % d == 0) { out += d; n /= d; }
return out;
}Explanation
Even though this looks like a copy-paste puzzle, the answer is pure number theory: the minimum number of operations equals the sum of the prime factors of n.
Why? To grow a block of p A's into a block of p times bigger, the cheapest move is one copy plus p - 1 pastes, which is p operations total. Multiplying the length by a prime p always costs exactly p ops, and any composite multiplier can be split into primes for the same or lower cost.
So we factor n and add up each prime, repeated as many times as it divides n. The loop tries each divisor d starting at 2; while d divides n it adds d to out and divides n by d with n //= d.
Once we peel off all copies of d, we increment d and continue until n shrinks to 1.
Example: n = 9 = 3 · 3. We add 3 then 3 again, giving out = 6, which matches the answer.