Minimum Operations
Lesson 3 of 11
3Minimum Operations
The “copy all and paste” puzzle that turns, after two lines of thinking, into prime factorisation.
What the picture shows: Copy then paste doubles the H, copy then two pastes triples it, so the count is the sum of the prime factors: 2 + 3 = 5.
Map of this part
The concepts in order, click any one to jump to it:
Two ways into the same idea
You have a text editor with one character and only two buttons: "copy all" and "paste". What is the fewest presses to reach a given number of characters? It looks like a puzzle about buttons, but after a little thought you find it is about breaking the number into smaller numbers that multiply together.
The answer is the sum of the prime factors of n: each factor p costs one copy and p - 1 pastes. You compute it by repeated division from 2 up to sqrt(n) in O(sqrt n) time, returning 0 when n <= 1.
Required fundamentals
Modulo and integer division
n % f asks "does it divide?" and n // f divides and drops the remainder. Those two operations are this solution's entire toolkit.
Primes and factors
A prime divides only by itself and 1. "Prime factorisation" means writing a number as a product of primes: 12 = 2 × 2 × 3.
A loop inside a loop, two conditions
The outer loop walks candidate factors; the inner one extracts the same factor again and again as long as it divides. Understanding that nesting is the solution.
The reframing skill
The most important thing in this part is not the code but the jump from "copy and paste" to "factor the number". Take your time with the concepts before writing a line.
Core concepts
The problem: a text file holds a single H. Your editor knows only two operations: Copy All and Paste. Find the fewest operations needed to reach exactly n characters.
1First observation: multiplication, not addition
Paste adds whatever you last copied, not one character. So if the file holds 3 characters and you copy them, every paste adds 3. You are not adding, you are multiplying.
Precisely: with x characters in the file, one copy and k - 1 pastes leaves you x · k characters and costs k operations (one copy plus k - 1 pastes).
k costs exactly k operations. No more, no less. The whole rest of the solution is built on that single sentence.2Second observation: the problem is factorisation
Since we start at 1 and multiply each time, reaching n means splitting it into factors: n = k₁ × k₂ × … × kₘ. The cost is the sum of those factors: k₁ + k₂ + … + kₘ.
So the question becomes: which split of n gives the smallest sum?
3Third observation: primes always win
Suppose one of your factors is composite, c = a × b with a and b both ≥ 2. Which is cheaper: one multiplication by a·b, or two, by a then by b?
| Comparison | Cost |
|---|---|
One multiplication by a × b | a · b |
Two: by a then by b | a + b |
| Difference | a·b − (a+b) = (a−1)(b−1) − 1 ≥ 0 for a, b ≥ 2 |
So splitting is never worse, and is strictly better from a, b ≥ 3. Keep splitting until you reach primes, which cannot be split. Conclusion: the answer is the sum of the prime factors of n, counted with multiplicity.
4A quick check against examples
n | Factorisation | Sum = answer | The route |
|---|---|---|---|
2 | 2 | 2 | copy, paste |
4 | 2 × 2 | 4 | ×2 then ×2 |
9 | 3 × 3 | 6 | ×3 then ×3 |
12 | 2 × 2 × 3 | 7 | ×2, ×2, ×3 |
13 | 13 | 13 | prime, no shortcut |
16 | 2⁴ | 8 | four multiplications by 2 |
100 | 2 × 2 × 5 × 5 | 14 | , |
5Edge cases and "impossible"
| Input | Output | Why |
|---|---|---|
n = 1 | 0 | The character is already there, zero operations |
n = 0 or negative | 0 | Unreachable, and the brief asks for 0 |
prime n | n | No split, one copy and n-1 pastes |
O(n log n) or worse, while factorisation is O(√n). When you notice a problem is mathematical, do not brute-force it.How it works
Three pictures: the code's path, then the actual route to n = 9 inside the editor, then a comparison of the different routes to n = 12.
Diagram 6, The code's path: an outer loop over candidate factors, an inner loop extracting the same factor while it divides.
Diagram 7, Reaching 9 characters: copy + two pastes (×3) then copy + two pastes (×3) = 6 operations, which is exactly 3 + 3.
Diagram 8, Different routes to 12 and what each costs: splitting into primes is cheapest, one big multiplication is dearest.
Worked example, step by step
The code is short; the idea is the hard part. Every output below is from a real run.
Step 1, the solution
#!/usr/bin/python3
"""0-minoperations"""
def minOperations(n):
"""Return the fewest Copy All / Paste operations needed to reach n H's."""
if not isinstance(n, int) or n <= 1:
return 0
operations = 0
factor = 2
while n > 1:
while n % factor == 0:
operations += factor
n //= factor
factor += 1
return operationsStep 2, running it
$ cat 0-main.py
#!/usr/bin/python3
minOperations = __import__('0-minoperations').minOperations
n = 4
print("Min # of operations to reach {} char: {}".format(n, minOperations(n)))
n = 12
print("Min # of operations to reach {} char: {}".format(n, minOperations(n)))
$ ./0-main.py
Min # of operations to reach 4 char: 4
Min # of operations to reach 12 char: 7Step 3, a full table of values
>>> for n in [1, 2, 3, 4, 9, 12, 13, 16, 100, 625, 0, -4]: ... print(n, minOperations(n)) 1 0 2 2 3 3 4 4 9 6 12 7 13 13 16 8 100 14 625 20 0 0 -4 0
Step 4, tracing n = 100 in detail
Factorising, one factor at a time
n = 100. We start with operations = 0 and factor = 2.
Does 100 divide by 2? Yes. operations = 2 and n = 50.
Again? Yes. operations = 4 and n = 25. A third time? 25 % 2 = 1, no.
factor = 3. Does 25 divide by 3? No. factor = 4.
Does 25 divide by 4? No. factor = 5.
(Note: we never check whether the factor is prime. Composite factors can never divide, because their own prime factors were removed before them.)
Does 25 divide by 5? Yes. operations = 9 and n = 5. Again? Yes. operations = 14 and n = 1.
n = 1, so the loop ends. The answer is 14 ✓
f, every smaller factor has been removed completely, so a composite number (4 or 6, say) can never divide n, its primes are already gone. That is an elegant point that saves you a whole function.factor * factor <= n, and then if n > 1 remains at the end it is a prime factor to add. That drops the complexity to O(√n). The solution above is O(n) in the worst case (a large prime), which is fine for this project's range.Myth vs. reality
| The myth | The reality |
|---|---|
| “This is a search problem, so I need to try every route.” | It is a mathematical problem with a closed-form answer: the sum of the prime factors. A search gives the same answer at far greater cost. |
| “Paste adds one character.” | Paste adds everything that was last copied. That single observation is the gateway to the whole solution. |
“Multiplying by k costs k - 1 operations.” | It costs k: one copy plus k - 1 pastes. Forgetting the copy is the most common arithmetic slip here. |
| “I should pick the biggest factor first to minimise the steps.” | The number of steps is not what is asked, the sum of the factors is. Reordering factors does not change their sum. |
“n = 1 is impossible, so return 0.” | You do return 0, but not because it is impossible: the character is already there, so no operation is needed. A difference in understanding, not in code. |
“I need an is_prime helper.” | You do not. Walking the factors in ascending order guarantees that whatever divides is always prime. |
Where it is used in practice
Cryptography
The difficulty of factoring a large number into primes is what RSA rests on. The same loop you wrote here, but for a 600-digit number, is the problem half the internet depends on.
Reducing operation cost
The same reasoning: if one composite operation costs more than two smaller ones that achieve the same thing, split it. That is a general performance idea, not specific to this puzzle.
Simplifying fractions and ratios
Greatest common divisors and fraction reduction rest on the same factorisation you just wrote.
Reframing problems
The transferable lesson: before writing code, ask "does this problem have a closed-form answer?" A yes saves you hours.
Try it yourself
What is minOperations(8), and why?
The prime factorisation of 8 is 2 × 2 × 2 and the sum is 6. The third option lands on the same 6 but through a non-prime split, right by coincidence here (4+2 = 6), though the correct reasoning is always primes. The actual route: ×2, ×2, ×2, i.e. three copies and three pastes.
Quick review flashcards
k cost?k operations: one copy and k - 1 pastes.n, counted with multiplicity.a + b <= a × b for a, b >= 2, so splitting is never worse.minOperations(12) = ?7, because 12 = 2×2×3 and 2+2+3 = 7.n <= 1?0, either the character is already there (n=1) or the target is unreachable.is_prime unnecessary?Check your understanding
1. Explain in one sentence why minOperations(9) == 6 and not 9.
Because 9 = 3×3, so we multiply by 3 twice at a cost of 3+3 = 6, instead of one multiplication by 9 costing 9. Splitting saves 3 operations.
2. Someone wrote operations += factor - 1. Where is the mistake?
They forgot the copy. Multiplying by factor needs one copy and factor-1 pastes, so the total is factor, not factor-1. This bug undercounts by exactly the number of factors.
3. (Spot the bug) The solution works but hangs for a large prime n such as 999983. Why?
The outer loop raises factor from 2 all the way to n itself, about a million turns. The fix: bound it with factor * factor <= n and then add the remaining n if it is greater than 1, which makes it O(√n).
4. Does the multiplication order change the cost? (×3 then ×2) or (×2 then ×3) for n = 6?
It does not: 3+2 = 2+3 = 5. Addition is commutative, so the cost depends on the set of factors, not their order. The file's intermediate contents do differ (3 characters or 2).
5. (Decision) Suppose the editor gained a third operation, "Paste ×2", costing one operation. Does the solution change?
Fundamentally yes, and the problem stops being factorisation. Every multiplication by k now costs less, so the trade-off shifts and you need dynamic programming or a fresh analysis. The lesson: a closed-form answer is conditional on the problem's exact rules, and changing one rule can demolish it.
Resources for this part
Sorted by kind: start with the official docs when you want the precise reference, or with an article or video when you want the explanation first.
Resources for this lesson
Grouped by type. Start with the official docs for precision, or an article or video for the explanation.
Articles2
Done with this lesson?
Sign in to save your progress.