N number of emoji using minimal keystrokes
This is an interview question, I could not solve it myself. Can anyone light it up?
Question: Suppose you have a chat client, in the text field you have one smiley face (it already is). Now you need this emoticon N times, and only two Copy and Paste operations are allowed. The result should be N smilies no more, no less. The copy is basically ^ a + ^ c. You always need to copy all the emoticons that are in the text box at a given time. Copy is one key press and paste is one key press. Write an algorithm / program for this problem. What will be the difficulty?
source to share
Whatever the number of emojis N, the coefficient N is the product of prime numbers. Then for each prime p in the factorization, you need to make one copy and p-1 paste. This is the minimum number of operations, if "copy" means you need to copy the entire line of emojis. The total number of operations is the sum of all prime factors in the factorization of N.
source to share
user2566092's answer is correct, but the statement
This is the minimum number of possible operations
claimed without evidence. Here's a formal justification.
Let n be the target number of emoticons. The configuration (r, k) consists of the number of r emojis in the result and the number of k emojis in the clipboard. Initial configuration (1, 0). From (r, k) the configurations (r, r) [copy] and (r + k, k) [paste] are reachable in one keystroke.
The next lemma implies that after the copy, the number of smileys as a result divides n evenly.
Lemma Suppose that g divides both r and k (g | r and g | k). Each configuration (r ', k') reachable from (r, k) satisfies g | r 'and g | k '.
Proof by induction. If the next step is a copy, then (r, r), then g | r and g | r. If the next step is paste, then (r + k, k), then g | r + k and g | k.
Now we can prove the main statement.
Theorem The minimum number of steps from (1, 0) to some (n, k), where k is arbitrary, equals p1 + p2 + ... + pm, where n = p1 p2 ... pm is a simple factorization.
User2566092's proof covered the upper bound: for i from 1 to m, copy once and paste pi - 1 time. The lower bound is obvious when n = 1. Otherwise, the best first action is clearly copy, (1, 1). We show by induction that the minimum number of steps from (1, 1) to (n, k) is p1 + p2 + ... + pm - 1.
From (1, 1), by the lemma, all we can do is insert until r divides n. We fix a certain r | n. The best sequences of actions from (r, r) to (n, n) and from (1, 1) to (n / r, n / r) are obviously the same. Without loss of generality, permuting the primes, assume that r = p1 p2 ... pj. Since ab> = a + b for a, b> = 2, then r> = p1 + p2 + ... + pj. If r <n, then the total cost by the inductive assumption is at least r + pj + 1 + pj + 2 + ... + pm - 1> = p1 + p2 + ... + pj - 1. If r = n, then the total cost is n - 1> = p1 + p2 + ... + pm - 1.
source to share
The program for the above problem is given below. The time complexity of this solution is O (n) in the worst case. The worst case occurs when the given number is prime.
#include <iostream>
using namespace std;
int main()
{
int smiles;
cin>>smiles;
int ans=0;
for(int i=2;i<=smiles;i++)
{
while(smiles%i==0)
{
ans+=i;
smiles/=i;
}
}
cout<<ans<<"\n";
return 0;
}
source to share