Example 2:

Input: n = 1
Output: 0

Example 3:

Input: n = 6
Output: 5
Explanation: We have 2 options:
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

Solution

Video Explanation

Here is the video explanation discussing different solutions we have covered below:

1c:T267e,

Method 1 - Using factors

In worst case we need to copy the character and paste it n-1 times to get the desired result. Now, lets see how we can minimize it, with different number of operations.

2 operations ⇨ copy + paste ⇨ we get AA (i.e. double). The ratio of operations to size is 2:2.
3 operations ⇨ copy + paste + paste ⇨ we get AAA (i.e. triple). The ratio of operations to size is 3:3.
4 operations ⇨ copy + paste + paste + paste ⇨ AAAA (i.e. quadruple). The ratio is 4:4.
5 operations
- copy + 4 X paste ⇨ AAAAA (i.e. 5 times)
- but, combining the two and three operations sequences can multiply the number of lines by 6 for the same number of operations. i.e. copy + paste ⇨ AA + copy + 2X paste ⇨ AAAAAA

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
Copy + 4 X Paste = AAAAA => 5 operations
Copy + 4 X Paste = AA...AA(25 As) => 5 operations, total operations = 10
Copy and paste – printed – AA...AAA (50 As) => 2 operations, total operations = 10 + 2 = 12

Code

[{"language":"Java","code":"public class Solution {\n    public int minSteps(int n) {\n        int steps = 0;\n        int factor = 2;\n\n        while (n > 1) {\n            while (n % factor == 0) { // check if problem can be broken in smaller problems\n                steps += factor; //if yes then add no of smaller problems to result. If number = 25  i = 5 then 5*5 = 25 so add 5 to results\n                n /= factor; // create smaller problem\n            }\n            factor++;\n        }\n\n        return steps;\n    }\n}","lang":"java"}]

Complexity

⏰ Time complexity: O(n)
🧺 Space complexity: O(1)

Method 2 - Recursion

The key insight is that copying isn't necessary every time; pasting multiple times after a copy is more efficient. For instance, to get 9 'A's, we might:

Start with 'A'
Copy All (clipboard: 'A')
Paste (now 'AA')
Copy All (clipboard: 'AA')
Paste (now 'AAAA')
Paste again (now 'AAAAAA')
Copy All (clipboard: 'AAAAAA')
Paste (now 'AAAAAAAAAAAA')

This example overshoots, highlighting the need for strategic copying and pasting. Thus, experimenting with different copy-paste combinations becomes vital, and recursion helps explore these combinations effectively.

Let's define our function f(i,j) more formally:

f(i,j) represents the minimum number of operations needed to generate n A's, starting with i A's on the screen and

Related Tags