# 2 Keys Keyboard
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/2-keys-keyboard)
Canonical: https://scaleengineer.com/dsa/problems/2-keys-keyboard
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Companies:** [Salesforce](https://scaleengineer.com/companies/salesforce)
---
## Problem
There is only one character `'A'` on the screen of a notepad. You can perform one of two operations on this notepad for each step:

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

Given an integer `n`, return _the minimum number of operations to get the character_ `'A'` _exactly_ `n` _times on the screen_.

**Example 1:**

**Input:** n = 3
**Output:** 3
**Explanation:** Initially, 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'.

**Example 2:**

**Input:** n = 1
**Output:** 0

**Constraints:**

* `1 <= n <= 1000`

# Approaches
## Dynamic Programming
A classic approach for optimization problems like this is Dynamic Programming. We can define a subproblem as finding the minimum steps to get `i` 'A's, let's call this `dp[i]`. To compute `dp[n]`, we can think about the last operation. It must have been a 'Paste'. If we pasted `k` characters, the screen must have had `n-k` characters before. This line of thought is complicated. A better way is to realize that to get `n` characters by pasting, we must have copied some number of characters `j` that is a divisor of `n`. The number of operations to go from `j` characters to `n` characters is `n/j` (1 for Copy, and `n/j - 1` for Paste). This gives us the recurrence relation: `dp[n] = min(dp[j] + n/j)` for all `j` that are divisors of `n`.
**Time:** O(n^2) - We have two nested loops. The outer loop runs from `i = 2` to `n`, and the inner loop runs from `j = i/2` to `1`. The total number of operations is roughly the sum of `i/2` for `i` from 2 to `n`, which is proportional to `n^2`. · **Space:** O(n) - We use a DP array of size `n+1` to store the results of subproblems.
**Pros:** Relatively straightforward to understand and implement.; Correctly solves the problem for the given constraints.
**Cons:** The time complexity of O(n^2) can be too slow if `n` is very large.; Requires O(n) space, which might be an issue for very large `n`.
### Explanation
We can build the solution iteratively from the bottom up. We'll use an array, `dp`, where `dp[i]` stores the minimum steps to achieve `i` 'A's. The base case is `dp[1] = 0` since we start with one 'A'. For any number `i`, the most straightforward (but not necessarily optimal) way to get `i` 'A's is to copy the initial 'A' and paste it `i-1` times, taking `i` steps. We use this as an initial value for `dp[i]`. Then, we try to find a better solution. To get `i` 'A's, we must have previously had `j` 'A's on the screen, where `j` is a divisor of `i`. We would then copy the `j` 'A's and paste them `(i/j) - 1` times. This sequence of a copy and multiple pastes takes `i/j` operations. So, the total steps would be `dp[j] + i/j`. We check this for all divisors `j` of `i` and take the minimum.

```java
class Solution {
    public int minSteps(int n) {
        if (n == 1) {
            return 0;
        }
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            dp[i] = i; // Initialize with the worst-case (copy 'A', paste i-1 times)
            for (int j = i / 2; j >= 1; j--) {
                if (i % j == 0) {
                    // To get i 'A's from j 'A's, it takes i/j operations.
                    // (1 Copy + (i/j - 1) Pastes)
                    dp[i] = Math.min(dp[i], dp[j] + i / j);
                }
            }
        }
        return dp[n];
    }
}
```
### Algorithm
- Create a `dp` array of size `n + 1`, where `dp[i]` will store the minimum number of operations to get `i` characters.
- Initialize `dp[1] = 0`. For all other `i`, initialize `dp[i] = i`, which represents the worst-case scenario (copying 'A' once and pasting `i-1` times).
- Iterate from `i = 2` to `n`.
- For each `i`, iterate through its possible divisors `j` from `1` up to `i/2`.
- If `j` is a divisor of `i`, it means we can obtain `i` characters from `j` characters. This involves one 'Copy All' operation on the `j` characters and then `(i/j) - 1` 'Paste' operations. The total number of operations for this step is `i/j`.
- The total operations to get `i` characters via this path is `dp[j] + i/j`.
- Update `dp[i]` with the minimum value found: `dp[i] = min(dp[i], dp[j] + i/j)`.
- After the loops complete, `dp[n]` will hold the minimum number of operations.

## Optimized Dynamic Programming
The previous DP approach can be optimized. Instead of iterating through `i` and finding all its divisors `j` to compute `dp[i]`, we can flip the logic. We can iterate through `i` and use `dp[i]` to update the `dp` values for all multiples of `i`. For a given `i`, we can reach `2*i`, `3*i`, `4*i`, etc. Reaching `j*i` from `i` takes `j` operations (one copy and `j-1` pastes). This way, each pair `(i, j)` is considered exactly once, leading to a more efficient calculation.
**Time:** O(n log n) - The total number of operations is the sum of `n/i` for `i` from 1 to `n`. This sum is `n * (1/1 + 1/2 + ... + 1/n)`, which is `n` times the n-th Harmonic number. The Harmonic series is approximately `log n`, so the complexity is `O(n log n)`. · **Space:** O(n) - We use a DP array of size `n+1`.
**Pros:** More efficient time complexity than the basic DP approach.; Still a systematic DP approach that is guaranteed to find the optimal solution.
**Cons:** Still requires O(n) space.; While more efficient than the basic DP, it's not the optimal solution.
### Explanation
This approach also uses a bottom-up dynamic programming strategy but with a more efficient state transition. We create a `dp` array of size `n+1`. We can initialize `dp[i]` to `i` (the worst-case steps) for `i > 1`, and `dp[1] = 0`. Then, we iterate from `i = 1` up to `n`. For each `i`, we iterate through multiples `i*j` (where `j` starts from 2). The cost to get `i*j` 'A's from `i` 'A's is `j` operations. So, we can update the minimum steps for `i*j` as `dp[i*j] = min(dp[i*j], dp[i] + j)`. This process resembles the Sieve of Eratosthenes, where we proactively update future values based on the current one.

```java
class Solution {
    public int minSteps(int n) {
        if (n == 1) {
            return 0;
        }
        int[] dp = new int[n + 1];
        // dp[1] is 0 by default
        for (int i = 2; i <= n; i++) {
            dp[i] = i; // Initialize with worst case
        }

        for (int i = 1; i <= n / 2; i++) {
            for (int j = 2; i * j <= n; j++) {
                dp[i * j] = Math.min(dp[i * j], dp[i] + j);
            }
        }
        return dp[n];
    }
}
```
### Algorithm
- Create a `dp` array of size `n + 1`.
- Initialize `dp[i] = i` for `i > 1` and `dp[1] = 0`.
- Iterate with `i` from `1` to `n`.
- For each `i`, we consider it as a building block. We can generate multiples of `i` by copying the `i` characters and pasting them.
- Start an inner loop with a multiplier `j` from 2. The target number of characters will be `m = i * j`.
- As long as `m <= n`, we can potentially update `dp[m]`. The number of steps to get `m` from `i` is `j` (1 copy, `j-1` pastes). The total steps are `dp[i] + j`.
- We update `dp[m] = min(dp[m], dp[i] + j)`.
- After the loops, `dp[n]` contains the result.

## Prime Factorization
The most efficient solution comes from a mathematical observation about the problem's structure. The minimum number of operations to get `n` 'A's is simply the sum of the prime factors of `n` (with multiplicity). For example, to get `n = 12` 'A's, the prime factorization is `2 * 2 * 3`. The minimum steps are `2 + 2 + 3 = 7`. This can be reasoned by considering that to get `n = p * m` characters, where `p` is a prime, the most efficient way is to first get `m` characters and then apply one 'Copy' and `p-1` 'Paste' operations, adding `p` steps. Applying this recursively, the total cost becomes the sum of all prime factors.
**Time:** O(sqrt(n)) - The algorithm performs trial division to find prime factors, which only needs to check for divisors up to the square root of `n`. · **Space:** O(1) - We only use a few variables to store the running sum and the current state of `n`.
**Pros:** Extremely efficient with O(sqrt(n)) time complexity.; Requires only O(1) space.; Simple and concise code.
**Cons:** The logic relies on a mathematical insight which might not be immediately obvious during an interview.
### Explanation
This approach transforms the problem from a dynamic programming puzzle into a number theory problem: finding the sum of prime factors of `n`. We can implement a standard prime factorization algorithm. We start with a divisor `d=2`. We repeatedly divide `n` by `d` as long as it's divisible, adding `d` to our total steps for each successful division. Once `n` is no longer divisible by `d`, we increment `d` and repeat. We only need to check for divisors up to `sqrt(n)`. If, after this process, `n` is still greater than 1, the remaining `n` must be a prime factor itself, so we add it to our total.

```java
class Solution {
    public int minSteps(int n) {
        int steps = 0;
        for (int d = 2; d * d <= n; d++) {
            while (n % d == 0) {
                steps += d;
                n /= d;
            }
        }
        if (n > 1) {
            steps += n;
        }
        return steps;
    }
}
```
### Algorithm
- Handle the base case: if `n` is 1, return 0.
- Initialize a variable `steps = 0` to accumulate the sum of prime factors.
- Iterate with a divisor `d` starting from 2, as long as `d*d <= n`.
- Inside the loop, use a `while` loop to check if `d` is a factor of the current `n`.
- While `n % d == 0`, it means `d` is a prime factor. Add `d` to `steps` and update `n` by dividing it by `d` (`n = n / d`).
- After the inner `while` loop, increment `d` to check the next potential factor.
- After the main loop finishes, if `n` is still greater than 1, it means the remaining value of `n` is a prime factor itself (e.g., if the original `n` was 14, after dividing by 2, `n` becomes 7, and the loop for `d` ends at `d=2`. The remaining `n=7` must be added).
- Add the remaining `n` to `steps`.
- Return `steps`.

# Solutions
### Java

```java
class Solution {
public
  int minSteps(int n) {
    int res = 0;
    for (int i = 2; n > 1; ++i) {
      while (n % i == 0) {
        res += i;
        n /= i;
      }
    }
    return res;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> f;
  int minSteps(int n) {
    f.assign(n + 1, -1);
    return dfs(n);
  }
  int dfs(int n) {
    if (n == 1)
      return 0;
    if (f[n] != -1)
      return f[n];
    int ans = n;
    for (int i = 2; i * i <= n; ++i) {
      if (n % i == 0) {
        ans = min(ans, dfs(n / i) + i);
      }
    }
    f[n] = ans;
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minSteps(self, n: int) -> int: @ cache def dfs(n): if n == 1: return 0 i, ans = 2, n while i * i <= n: if n % i == 0:  # factor `i` can be used as the number of modules # n // i, length of the module `n/i` ans = min ( ans , dfs ( n // i ) + i ) i += 1 return ans return dfs ( n ) ############ # iteration class Solution : def minSteps ( self , n : int ) -> int : res = 0 i = 2 while n > 1 : while n % i == 0 : res += i n //= i i += 1 return res ############ """ 1. group operations as ([^C][^V][^V]...[^V]) that has in total k operations and it gets k * # of A 2. n can be written as x_1 * x_2 * ... * x_N 3. then total operations # = x_1 + x_2 + ... + x_N 4. since p * q >= p + q for integers > 1, to min the result 5. decomposite x_1 to x_N to min the sum """ ''' `yield` is a keyword that is used like return, except the function will return a generator. https://stackoverflow.com/questions/231767/what-does-the-yield-keyword-do-in-python ''' class Solution ( object ): def _minSteps ( self , n ): """ :type n: int :rtype: int """ if n == 1 : return 0 for i in range ( 2 , int (( n + 1 ) ** 0.5 ) + 1 ): if n % i == 0 : return i + self . minSteps ( n / i ) return n def minSteps ( self , n ): def factor ( n ): d = 2 while d * d <= n : while n % d == 0 : n /= d yield d d += 1 if n > 1 : yield n return sum ( factor ( n ))

```