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.

&nbsp;
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


&nbsp;
Constraints:


	1 &lt;= n &lt;= 1000


class Solution:
    def minSteps(self, n: int) -> int:      
        # at every step we can copy or paste
        # paste -> we need to know the current clipboard content (count)
        # copy -> set clipboard count to current screen count (we should consider it, if the last operation was paste)
        
        memo = {}
        
        def dfs(clipboard_count, screen_count):
            if (clipboard_count, screen_count) in memo:                   
                return memo[(clipboard_count, screen_count)]
            
            # we reached n, this is a valid option
            if screen_count == n: return 0
            
            # we passed n, not a valid option
            if screen_count > n: return float('inf')                
            
            # paste or copy
            copy_opt = paste_opt = float('inf')
            
            # we should only paste if clipboard is not empty
            if clipboard_count > 0:
                paste_opt = dfs(clipboard_count, screen_count + clipboard_count)             
            
            # we should consider copy only if the last operation was paste
            if screen_count > clipboard_count:
                copy_opt = dfs(screen_count, screen_count) 
            
            # save to memo
            memo[(clipboard_count, screen_count)] = 1 + min(paste_opt, copy_opt)            
            return memo[(clipboard_count, screen_count)]
            
        return dfs(0, 1)
            
class Solution {
    public int minSteps(int n) {
        int rem = n-1, copied = 0, ans = 0, onScreen = 1;
        
        while(rem>0){
            if(rem % onScreen == 0){
                ans++; // copy operation
                copied = onScreen;   
            }
            rem-=copied;
            ans++; // paste operation
            onScreen = n-rem; // no. of characters on screen currently that can be copied in next copy operation
        }
        
        return ans;
    }
}
class Solution {
public:
//See the solution for this explanation 
    int byPrimeFactorization(int n) {
        if(n == 1)
            return 0;
        if(n == 2)
            return 2;
        int factor = 2, ans = 0;
        while(n > 1) {
            while(n % factor == 0) {
                ans += factor;
                n /= factor;
            }
            factor++;
        }
        return ans;
    }
   
    int byDp(int n) {
        vector<int> dp(1001, INT_MAX);
        dp[0] = dp[1] = 0;
        dp[2] = 2, dp[3] = 3;
        for(int i = 4; i <= n; i++) {
            dp[i] = i; //maximum number of operations required will be i
            for(int j = 2; j <= i / 2; j++) { //we copy and paste j A's till we have i A's
                int x = i - j; //we already have j A's in our stream, so remaining = i - j
                if(x % j == 0) { //if remaining number of A's is a multiple of J
                    dp[i] = min(dp[i], dp[j] + 1 + (x / j)); //1 operation to copy, x / j to paste, dp[j] for getting j A's
                }
            }
        }
        return dp[n];
    }
    
    int minSteps(int n) {
        return byPrimeFactorization(n);
    }
};
var minSteps = function(n) {
	let result = 0;

	for (let index = 2; index <= n; index++) {
		while (n % index === 0) {
			result += index;
			n /= index;
		}
	}
	return result;
};
2 Keys Keyboard