# 2 Keys Keyboard

## Description

Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:

1. `Copy All`: You can copy all the characters present on the notepad (partial copy is not allowed).
2. `Paste`: You can paste the characters which are copied **last time**.

Given a number `n`. You have to get **exactly** `n` 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get `n` 'A'.

**Example 1:**

```
Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.
```

**Note:**

1. The `n` will be in the range \[1, 1000].

## Solutions

### My solution

Let `dp[i, j]` be the minimum number of steps to get i `A`s on the notepad with j `A`s on the clipboard. Let `dp[i]` be the minimum number of steps to get  i `A`s on the notepad.

$$dp\[i] = \min\_{0 < j < i} dp\[i, j]$$

$$dp\[i,j]$$ is undefined if $$i < j$$, because the clipboard cannot have more `A` than the notepad.&#x20;

If $$i == j$$, $$dp\[i,j] = dp\[i, i] = dp\[i] + 1.$$ (+1 for the copy operation)

If $$i > j$$,  $$dp\[i,j]=dp\[i-j,j] + 1$$. (+1 for the paste operation)

```cpp
class Solution {
public:
    int minSteps(int n) {
        if(n == 1) return 0;
        // previous action must be paste
        int min_step = 1000;
        for(int m = 1; 2 * m <= n; ++m){
            // paste m characters
            int step = minSteps(n - m, m);
            if(step < min_step)
                min_step = step;
        }
        return min_step + 1;
    }
    
    // n 'A's on the notepad, m 'A's on the clipboard
    int minSteps(int n, int m){
        if(n < m){
            // not possible
            return 1000;
        }else if(n > m){
            // previous action must be paste, i.e., paste m 'A's
            return minSteps(n - m, m) + 1;
        }else{
            // must be copy
            return minSteps(n) + 1;
        }
    }
};
```

Dynamic programming solution.

```cpp
class Solution {
public:
    int minSteps(int n) {
        vector<int> dp1(n + 1, n); // dp1[i] = minimum steps to get i 'A's on the notepad.
        dp1[1] = 0;
        // dp2[i][j] = minimum steps to get i 'A's on the notepad and j 'A's on the clipboard
        vector<vector<int>> dp2(n + 1, vector<int>(n + 1, n));
        for(int i = 1; i <= n; ++i){
            for(int j = 1; 2 * j <= i; ++j){
                dp2[i][j] = dp2[i - j][j] + 1; // paste j 'A'
                dp1[i] = min(dp1[i], dp2[i][j]);
            }
            dp2[i][i] = dp1[i] + 1; // copy i 'A' to the clipboard
        }
        return dp1[n];
    }
};
```

### Optimal solution

For any sequence of moves that produces n `A`s, break it into groups of `(copy, paste, paste, ..., paste)`.

Say these groups have lengths $$l\_1,l\_2, \cdots, l\_m$$. After performing the moves in the first group, there are $$l\_1$$ `A`s. After performing the moves in the second group, there are $$l\_1 \cdot l\_2$$ `A`s. At the end, there are $$l\_1 \cdot l\_2 \cdot \ldots \cdot l\_m = n$$ `A`s.

If any group has a length that is a composite number, say $$p \cdot q$$, we can break it into two smaller groups. The first group is 1 copy followed by $$p -1$$ pastes. And the second group is 1 copy followed by $$q - 1$$ pastes. The number of moves does not increase because $$p + q \le p \cdot q$$ for $$p, q \ge 2$$.

So the minimum number of moves to get n `A` s is the sum of the prime factors of `n`.

```cpp
class Solution {
public:
    int minSteps(int n) {
        int count = 0;
        for(int i = 2; i <= n; ++i){
            while(n % i == 0){
                count += i;
                n /= i;
            }
        }
        return count;
    }
};
```