LeetCode 650: 2 Keys Keyboard

Problem Restatement

We start with one character:

"A"

We can perform two operations:

Operation	Meaning
Copy All	Copy the entire current text
Paste	Paste the copied text

We need to produce exactly n characters "A" using the minimum number of operations.

Return that minimum number.

The initial "A" already exists and does not count as an operation.

Input and Output

Item	Meaning
Input	Integer n
Output	Minimum operations needed to produce exactly n "A" characters
Initial state	One "A" already exists
Allowed operations	Copy All and Paste

Example function shape:

def minSteps(n: int) -> int:
    ...

Examples

Example 1:

n = 3

Operations:

Step	Operation	Text
Start	none	A
1	Copy All	A
2	Paste	AA
3	Paste	AAA

Total operations:

3

Example 2:

n = 1

We already have one "A".

No operations are needed.

Output:

0

First Thought: Dynamic Programming by State

A direct idea is:

dp[i]

meaning:

minimum operations needed to produce i characters

Suppose we want to reach i.

If some smaller number j divides i, then:

1. Build j characters.
2. Copy All once.
3. Paste (i / j - 1) times.

That costs:

dp[j] + 1 + (i // j - 1)

which simplifies to:

dp[j] + i // j

This leads to a valid DP solution.

Key Insight

The operations naturally form multiplication.

Suppose we currently have:

j

characters.

After:

1 Copy All
k Paste operations

we get:

j * (k + 1)

characters.

So every construction step multiplies the current amount.

This leads to an important observation:

Breaking n into factors minimizes the total number of operations.

For example:

n = 9

We could do:

1 -> 9

using:

Copy + 8 pastes = 9 operations

But a better plan is:

1 -> 3 -> 9

Cost:

Step	Operations
1 -> 3	3
3 -> 9	3

Total:

6

The factorization:

9 = 3 * 3

matches the operation cost:

3 + 3 = 6

This pattern generalizes.

Prime Factorization Insight

Suppose:

n = a * b

We can:

1. Build a characters.
2. Copy once.
3. Paste b - 1 times.

Cost:

cost(a) + b

Then we recursively factor a.

Eventually, the optimal solution becomes:

sum of prime factors of n

For example:

n = 12

Prime factorization:

12 = 2 * 2 * 3

Minimum operations:

2 + 2 + 3 = 7

Construction:

Step	Operations
1 -> 2	2
2 -> 4	2
4 -> 12	3

Total:

7

Greedy Prime Factorization Algorithm

We repeatedly divide by the smallest factor.

1. Initialize answer = 0.
2. Start with divisor d = 2.
3. While d * d <= n:
   1. While d divides n:
      1. Add d to the answer.
      2. Divide n by d.
   2. Increase d.
4. If n > 1, add the remaining prime factor.
5. Return the answer.

Implementation

class Solution:
    def minSteps(self, n: int) -> int:
        answer = 0
        divisor = 2

        while divisor * divisor <= n:
            while n % divisor == 0:
                answer += divisor
                n //= divisor

            divisor += 1

        if n > 1:
            answer += n

        return answer

Code Explanation

We start with:

answer = 0
divisor = 2

The divisor scans possible prime factors.

Whenever:

n % divisor == 0

the divisor is part of the factorization.

We add that factor to the answer:

answer += divisor

Then remove it from n:

n //= divisor

We keep dividing while the factor still exists.

At the end:

if n > 1:
    answer += n

handles the remaining prime factor larger than sqrt(original_n).

Why Prime Factors Give the Minimum

Suppose we want to multiply the current amount by:

x

This requires:

Operation	Count
Copy All	1
Paste	x - 1

Total:

x

operations.

Now suppose:

x = a * b

with:

a > 1
b > 1

Then instead of multiplying by x in one step, we can multiply by a and then by b.

Cost:

a + b

Since:

a + b <= a * b

for integers greater than 1, breaking a composite factor into smaller factors never increases the cost.

Therefore, the minimum cost is achieved when all factors are prime.

Thus the optimal number of operations equals the sum of the prime factors of n.

Correctness

Each sequence of operations can be viewed as repeatedly multiplying the current number of characters.

If we multiply by some factor f, we must perform:

Operation	Count
One Copy All	1
Paste operations	f - 1

for a total cost of:

f

Therefore, any construction of n corresponds to a factorization of n, and the total operation count equals the sum of those factors.

If some factor is composite:

f = a * b

then replacing f with a and b changes the cost from:

f

to:

a + b

Since:

a + b <= a * b = f

for integers greater than 1, decomposing composite factors never increases the cost.

Thus the minimum total cost is achieved when all factors are prime.

The algorithm computes exactly the sum of the prime factors of n, including multiplicity, so it returns the minimum number of operations.

Complexity

Let n be the input value.

Metric	Value	Why
Time	O(sqrt(n))	Trial division up to square root
Space	O(1)	Only a few variables are used

Alternative Dynamic Programming Solution

We can also use DP directly.

class Solution:
    def minSteps(self, n: int) -> int:
        dp = [0] * (n + 1)

        for i in range(2, n + 1):
            dp[i] = i

            for j in range(i // 2, 1, -1):
                if i % j == 0:
                    dp[i] = dp[j] + i // j
                    break

        return dp[n]

Explanation:

If:

j divides i

then:

1. Build j.
2. Copy once.
3. Paste until reaching i.

Cost:

dp[j] + i // j

Metric	Value
Time	O(n²) worst case
Space	O(n)

The prime-factor solution is simpler and faster.

Testing

def run_tests():
    s = Solution()

    assert s.minSteps(1) == 0
    assert s.minSteps(2) == 2
    assert s.minSteps(3) == 3
    assert s.minSteps(4) == 4
    assert s.minSteps(5) == 5
    assert s.minSteps(6) == 5
    assert s.minSteps(9) == 6
    assert s.minSteps(12) == 7
    assert s.minSteps(18) == 8

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
1	Already complete
Prime numbers	Cost equals the prime itself
4 = 2 * 2	Factorization reduces operations
6 = 2 * 3	Mixed prime factors
9 = 3 * 3	Repeated prime factor
12 = 2 * 2 * 3	Multiple factors
18 = 2 * 3 * 3	Larger composite example