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

**Copy All**– This operation will copy all the printed characters.**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 – 6Option 2: Copy All – this will copy ‘A’ Paste – output “AA” Paste – output “AAA” Copy All Paste – output “AAAAAA”Total operations – 5Since 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**:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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