LeetCode 650: 2 Keys Keyboard

Problem Restatement

We start with one character:

"A"

We can perform two operations:

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

Example function shape:

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

Examples

Example 1:

n = 3

Operations:

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:

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:

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:

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:

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.

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

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: