Abstract / Summary

Given a target string and an initial string a, find the minimum number of operations to get the target using copy all and paste operations.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 59% (500k+ submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a method minSteps that computes a numeric result based on the prime factorization of the input integer n. The algorithm treats the problem as a sum of prime factors, where each factor contributes its value to a running total called steps. The method handles the trivial case where n equals 1, performs an efficient trial-division factorization, and aggregates the contributions of all prime factors, including any remaining prime larger than the square root of the original number.

Core Logic

The function begins with a guard clause that immediately returns 0 when the input is 1. This reflects the fact that no steps are required for the base case.

if n == 1:
    return 0

The next section initializes two variables: steps, which accumulates the result, and i, the divisor used for trial division. The outer loop iterates while i*i does not exceed the current value of n. This condition ensures that the loop only runs up to the square root of the current n, which shrinks as factors are removed.

steps = 0
i = 2
while i*i <= n:
    ...
    i += 1

Inside the outer loop, an inner loop repeatedly divides n by the current divisor i as long as i is a factor. Each division corresponds to adding the divisor’s value to steps. By continuously dividing out the same factor, the algorithm captures the multiplicity of each prime factor without needing a separate count variable.

while n % i == 0:
    steps += i
    n //= i

After the inner loop finishes for a particular i, the divisor is incremented, and the outer loop proceeds to test the next candidate. Because n is reduced each time a factor is found, the condition i*i <= n may become false earlier than it would in a naïve implementation that keeps n unchanged.

When the outer loop terminates, any residual value of n greater than 1 must be a prime factor that is larger than the square root of the original number. The algorithm adds this final prime directly to steps.

if n > 1:
    steps += n

Finally, the accumulated steps value is returned as the result.

return steps

Edge Cases Handled

The early return for n == 1 correctly handles the smallest possible input, ensuring that the function does not enter the factorization loops unnecessarily.

When n is a prime number, the outer loop will not find any divisor less than or equal to its square root, leaving n unchanged. The subsequent conditional block adds the prime itself to steps, yielding the correct result for prime inputs.

If n contains repeated prime factors (for example, n = 12 which factors into 2 * 2 * 3), the inner while loop captures each occurrence by repeatedly adding the divisor and dividing n. This correctly accounts for multiplicities without extra bookkeeping.

Large composite numbers with many small factors are efficiently reduced because each division shrinks n, potentially shortening the remaining search space for subsequent divisors.

Performance Optimizations

The algorithm employs trial division only up to the square root of the current n, rather than the original input value. By updating n each time a factor is removed, the bound i*i <= n can become false earlier, reducing the number of iterations required for numbers with small factors.

Incrementing the divisor i by one each iteration keeps the implementation simple while still benefiting from the early termination condition.

The inner loop’s direct division and accumulation avoid the need for auxiliary data structures, keeping the memory footprint minimal and the execution path tight.

Overall, the method balances readability with an effective reduction of unnecessary work, especially for inputs that have a rich factor structure.

Imagine you have a magical machine that prints stickers. You want to print exactly the number of stickers that match your friend's age, and you want to do it in the fewest number of clicks possible.

The machine works in a special way. You can only do two things. First, you can copy all the stickers currently on a page onto your clipboard. Second, you can paste those copied stickers onto your page.

This code acts like a tiny brain figuring out the quickest way to get to that number of stickers. It starts by looking for small groups of stickers that can be multiplied together to equal your target number. Think of it like breaking a big number apart into smaller building blocks.

The computer starts testing the smallest numbers to see if they fit into the total like puzzle pieces. Every time it finds a piece that fits perfectly, it imagines copying and pasting that many stickers. It keeps track of how many moves this takes by adding those numbers up in a little pile called steps.

It keeps shrinking the target number as it finds these building blocks. Once the number has been broken down as much as it can possibly go, it adds up all the moves it counted during the process to give the final answer for how many clicks are needed. It is just like finding the shortest path to a treasure chest by hopping across the right stepping stones.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: sublinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Python			Java	TS
	WalkCCC	C++		Python			Java
	leetcode.ca	C++	JS	Python		Go	Java	TS
	LeetcodeHelp	C++		Python			Java
	Progiez	C++		Python			Java
github	everthis		JS
	fsq	C++
	JoshCrozier		JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007			Python
	lzl124631x	C++
	sonugiri1043	C++
	suxrobGM				C#
	wisdompeak	C++
	withaarzoo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
lzl124631x	C++
sonugiri1043	C++
suxrobGM	C#
wisdompeak	C++
withaarzoo	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality