Problem

There is only one character 'A' on the screen of a notepad. You can perform one of two operations on this notepad for each step:

  • Copy All: You can copy all the characters present on the screen (a partial copy is not allowed).
  • Paste: You can paste the characters which are copied last time.

Given an integer n, return the minimum number of operations to get the character 'A' exactly n times on the screen.

Examples

Example 1:

Input: n = 3
Output: 3
Explanation: Initially, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

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:

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

Java
public class Solution {
    public int minSteps(int n) {
        int steps = 0;
        int factor = 2;

        while (n > 1) {
            while (n % factor == 0) { // check if problem can be broken in smaller problems
                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 /= factor; // create smaller problem
            }
            factor++;
        }

        return steps;
    }
}

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:

  1. Start with ‘A’
  2. Copy All (clipboard: ‘A’)
  3. Paste (now ‘AA’)
  4. Copy All (clipboard: ‘AA’)
  5. Paste (now ‘AAAA’)
  6. Paste again (now ‘AAAAAA’)
  7. Copy All (clipboard: ‘AAAAAA’)
  8. 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 j A’s in the clipboard.

Our objective is to find ( f(1, 1) ), which means starting with one ‘A’ on the screen and one ‘A’ in the clipboard.

At each step, we have two options:

  1. Copy All and Paste:
    • Takes 2 steps (1 Copy, 1 Paste).
    • Transforms state from (i,j) to (2i, i).
    • Total operations: 2 + f(2i, i) )
  2. Paste Only:
    • Takes 1 step.
    • Transforms state from (i,j) to (i + j, j).
    • Total operations: 1 + f(i + j, j).

Thus, the recurrence relation is: $$ f(i, j) = \min(2 + f(2i, i), 1 + f(i + j, j)) $$

This relation captures the essence of choosing the minimum number of operations between the two options at each step.

Base cases:

  • If ( i = n ), we’ve achieved our goal, so ( f(n, j) = 0 ) for any j.
  • If ( i > n ), we’ve overshot, so return a very large number (effectively infinity).

Code

Java
public class Solution {
    private static final int INF = 1001; // Define a large number to denote invalid paths

    public int minSteps(int n) {
        if (n == 1) {
            return 0; // We already have one 'A', so no operations needed
        }
        return 1 + findMinSteps(1, 1, n); // Start with one 'A' on screen and in clipboard
    }

    private int findMinSteps(int currLen, int clipboardLen, int n) {
        if (currLen == n) {
            return 0; // We've reached our goal, no more operations needed
        }
        if (currLen > n) {
            return INF; // We've overshot, this path is invalid
        }

        // Try Copy All and Paste
        int copyAndPaste = 2 + findMinSteps(currLen * 2, currLen, n);

        // Try Paste only
        int pasteOnly = 1 + findMinSteps(currLen + clipboardLen, clipboardLen, n);

        // Return the minimum of the two options
        return Math.min(copyAndPaste, pasteOnly);
    }
}

Complexity

  • ⏰ Time complexity: O(2^n) because at each step we have 2 options to choose from and then we take min.
  • 🧺 Space complexity: O(n)

Method 3 - Top Down DP

Code

Java
public class Solution {
    private static final int INF = 1001; // Define a large number to denote invalid paths
	private int[][] cache;
    public int minSteps(int n) {
        if (n == 1) {
            return 0; // We already have one 'A', so no operations needed
        }
        this.cache = new int[n + 1][n / 2 + 1];
        return 1
            + findMinSteps(1, 1, n); // Start with one 'A' on screen and in clipboard
    }

    private int findMinSteps(int currLen, int clipboardLen, int n) {
        if (currLen == n) {
            return 0; // We've reached our goal, no more operations needed
        }
        if (currLen > n) {
            return INF; // We've overshot, this path is invalid
        }
        if (cache[currLen][clipboardLen] != 0) {
            return cache[currLen][clipboardLen];
        }        

        // Try Copy All and Paste
        int copyAndPaste = 2 + findMinSteps(currLen * 2, currLen, n);

        // Try Paste only
        int pasteOnly = 1 + findMinSteps(currLen + clipboardLen, clipboardLen, n);

        // Return the minimum of the two options
        int ans = Math.min(copyAndPaste, pasteOnly);
        cache[currLen][clipboardLen] = ans;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2)
    • In the worst case, we might need to fill out our entire cache. The cache has dimensions n × (n/2), where n is our target length. For each cell, we’re doing constant time operations. Therefore, our time complexity is O(n * n/2) = O(n^2).
  • 🧺 Space complexity: O(n^2) assuming recursion stack and using cache

Method 4 - Bottom up DP

Code

Java
public class Solution {
    private static final int INF = 1001;

    public int minSteps(int n) {
        if (n == 1) {
            return 0; // We already have one 'A', so no operations needed
        }

        int[][] dp = new int[n + 1][n + 1];

        // Initialize DP table with a large number to denote invalid paths
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = INF;
            }
        }

        // Starting point
        dp[1][0] = 0;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                // Paste Operation
                if (i + j <= n) {
                    dp[i + j][j] = Math.min(dp[i + j][j], dp[i][j] + 1);
                }
                // Copy All and Paste Operation
                if (i * 2 <= n) {
                    dp[i * 2][i] = Math.min(dp[i * 2][i], dp[i][j] + 2);
                }
            }
        }

        int minSteps = INF;
        for (int i = 0; i <= n; i++) {
            minSteps = Math.min(minSteps, dp[n][i]);
        }

        return minSteps;
    }

}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(n^2) for using dp array

Method 5 - Optimized Bottom up DP

Code

Java
class Solution {
    public int minSteps(int n) {
        if (n == 1) {
	        return 0;
	    }
        int[] dp = new int[n + 1];
        
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
	        dp[i] = i;
            for (int j = i / 2; j >= 1; j--) {
                if (i % j == 0) {
	                //  steps to previous number + copy + paste
                    dp[i] = dp[j] + 1 + ((i / j) - 1);
                    break;
                }
            }
        }
        
        return dp[n];
    }
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(n)