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 As on the notepad with j As on the clipboard. Let dp[i] be the minimum number of steps to get i As 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.

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)

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.

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 As, 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$ As. After performing the moves in the second group, there are $l_1 \cdot l_2$ As. At the end, there are $l_1 \cdot l_2 \cdot \ldots \cdot l_m = n$ As.

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.

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;
    }
};