# 2 Keys Keyboard Problem

2 Keys Keyboard ProblemGiven a positive integer N and a string S initially it is “A”, the task is to minimize the number of operations required to form a string consisting of N numbers of A’s by performing one of the following operations in each step:Copy all the characters present in the string S.Append all the characters to the string S which are copied last time.Examples:Input: N = 3Output: 3Explanation:Below are the operations performed:Operation 1: Copy the initial string S once i.e., “A”.Operation 2: Appending the copied string i.e., “A”, to the string S modifies the string S to “AA”.Operation 3: Appending the copied string i.e., “A”, to the string S modifies the string S to “AAA”.Therefore, the minimum number of operations required to get 3 A’s is 3.Input: N = 7Output: 7Approach: The given problem can be solved based on the following observations: If N = P1*P2*Pm where {P1, P2, …, Pm} are the prime numbers then one can perform the following moves:First, copy the string and then paste it (P1 – 1) times.Similarly, again copying the string and pasting it for (P2 – 1) times.Performing M times with the remaining prime number, one will get the string with N number of A’s.Therefore, the total number of minimum moves needed is given by (P1 + P2 + … + Pm).Follow the steps below to solve the problem:Below is the implementation of the above approach:C++  #include using namespace std;  int minSteps(int N){        int ans = 0;          for (int d = 2; d * d