# LeetCode 650: 2 Keys Keyboard

## Problem Restatement

We start with one character:

```text
"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:

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

## Examples

Example 1:

```python
n = 3
```

Operations:

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

Total operations:

```python
3
```

Example 2:

```python
n = 1
```

We already have one `"A"`.

No operations are needed.

Output:

```python
0
```

## First Thought: Dynamic Programming by State

A direct idea is:

```python
dp[i]
```

meaning:

```text
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:

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

which simplifies to:

```python
dp[j] + i // j
```

This leads to a valid DP solution.

## Key Insight

The operations naturally form multiplication.

Suppose we currently have:

```python
j
```

characters.

After:

```python
1 Copy All
k Paste operations
```

we get:

```python
j * (k + 1)
```

characters.

So every construction step multiplies the current amount.

This leads to an important observation:

```text
Breaking n into factors minimizes the total number of operations.
```

For example:

```python
n = 9
```

We could do:

```text
1 -> 9
```

using:

```text
Copy + 8 pastes = 9 operations
```

But a better plan is:

```text
1 -> 3 -> 9
```

Cost:

| Step | Operations |
|---|---:|
| `1 -> 3` | `3` |
| `3 -> 9` | `3` |

Total:

```python
6
```

The factorization:

```python
9 = 3 * 3
```

matches the operation cost:

```python
3 + 3 = 6
```

This pattern generalizes.

## Prime Factorization Insight

Suppose:

```python
n = a * b
```

We can:

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

Cost:

```python
cost(a) + b
```

Then we recursively factor `a`.

Eventually, the optimal solution becomes:

```text
sum of prime factors of n
```

For example:

```python
n = 12
```

Prime factorization:

```python
12 = 2 * 2 * 3
```

Minimum operations:

```python
2 + 2 + 3 = 7
```

Construction:

| Step | Operations |
|---|---:|
| `1 -> 2` | `2` |
| `2 -> 4` | `2` |
| `4 -> 12` | `3` |

Total:

```python
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

```python
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:

```python
answer = 0
divisor = 2
```

The divisor scans possible prime factors.

Whenever:

```python
n % divisor == 0
```

the divisor is part of the factorization.

We add that factor to the answer:

```python
answer += divisor
```

Then remove it from `n`:

```python
n //= divisor
```

We keep dividing while the factor still exists.

At the end:

```python
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:

```python
x
```

This requires:

| Operation | Count |
|---|---:|
| Copy All | `1` |
| Paste | `x - 1` |

Total:

```python
x
```

operations.

Now suppose:

```python
x = a * b
```

with:

```python
a > 1
b > 1
```

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

Cost:

```python
a + b
```

Since:

```python
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:

```python
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:

```python
f = a * b
```

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

```python
f
```

to:

```python
a + b
```

Since:

```python
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.

```python
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:

```python
j divides i
```

then:

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

Cost:

```python
dp[j] + i // j
```

| Metric | Value |
|---|---:|
| Time | `O(n²)` worst case |
| Space | `O(n)` |

The prime-factor solution is simpler and faster.

## Testing

```python
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 |