Minimum Copy Paste Operations

Objective: You have given a character ‘A’ which is already printed. You are allowed to perform only 2 operations –

  1. Copy All – This operation will copy all the printed characters.
  2. Paste – This operation will paste all the characters which are already copied.

Given a number N, write an algorithm to print character ‘A’ exactly N times with minimum no of operations (either copy all or paste)

Example:

Character – A
N = 6

Option 1:
Copy All – this will copy ‘A’
Paste – output “AA”
Paste – output “AAA”
Paste – output “AAAA”
Paste – output “AAAAA”
Paste – output “AAAAAA”
Total operations – 6

Option 2:
Copy All – this will copy ‘A’
Paste – output “AA”
Paste – output “AAA”
Copy All
Paste – output “AAAAAA”
Total operations – 5

Since with option 2, the task is done in 5 operations. Minimum operations – 5

Approach:

In worst case we need to copy the character and paste it N-1 times to get the desired result.

Since we want to reduce the number of operations we need to reduce the paste operations where ever it is possible which means perform the copy operation. Say If N = 50 then we print 25 A’s then by doing copy all and paste will print 50 characters. Now to reach 25, which is multiple of 5 so if we print 5 A’s then copy and paste it 4 times to get 25 A’s and now to print 5 A’s, copy the already printed A and paste it 4 times.

N = 50, printed – A

Copy and paste it 4 times – printed – AAAAA, operations – 5
Copy and paste it 4 times – printed AA…..AA (25), operations – 5 + 5 = 10
Copy and paste – printed – AA…AAA (50 A’s), operations – 10 + 2 = 12

Code:

public class MinimumCopyPasteDP {
public int find(int number){
int res = 0;
for(int i=2;i<=number;i++){
while(number%i == 0){ //check if problem can be broken into smaller problem
res+= i; //if yes then add no of smaller problems to result. If number = 25 i = 5 then 5*5 = 25 so add 5 to results
number=number/i; // create smaller problem
}
}
return res;
}
public static void main(String[] args) {
MinimumCopyPasteDP m = new MinimumCopyPasteDP();
int n = 50;
System.out.println("Minimum Operations: " + m.find(n));
}
}


Output:

Minimum Operations: 12