650. 2 Keys Keyboard

Problem Description

The given problem describes a situation where we have a notepad that initially contains only one character, 'A'. We are allowed to perform two operations:

Copy All: You can copy everything present on the screen at that moment.
Paste: You can paste the last copied set of characters onto the screen.

The objective is to figure out the minimum number of operations needed to get exactly 'n' occurrences of 'A' on the screen. We are to return this minimum number of operations.

Intuition

To approach this problem, we need to think in terms of how we can build up 'n' characters from the initial single 'A' in the least number of steps. Intuitively, pasting the same characters repeatedly seems like an efficient way to reach our goal. However, we can only paste what we've last copied, and we can't do a partial copy.

Given this constraint, a key insight is understanding that getting to 'n' 'A's efficiently often means generating 'A's in multiples that are factors of 'n'. If we can create a sequence where we copy 'x' 'A's and then paste them (n/x - 1) times, we will end up with 'n' characters in fewer steps, especially if 'x' is large.

The solution is recursive in nature and works by dividing the problem into smaller subproblems. Each time we come across a factor 'i' of 'n', we can consider the minimum number of steps required to get 'i' number of 'A's and then add the steps required to copy it (which is 'i') and paste it (n/i - 1) times to complete the 'n' characters.

The function uses memoization (via the @cache decorator), to store and reuse the results of subproblems which drastically reduces the number of redundant calculations, effectively improving performance.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The solution applies a depth-first search (DFS) strategy to solve the problem by breaking it into smaller subproblems. The dfs function is a recursive function that finds the minimum number of operations for a given target n.

The base case of the recursion is when n equals 1, at which point no further operations are required (return 0).

For other values of n, the function iterates over possible factors of n starting from 2 (since 1 would not reduce the problem), checking if n % i == 0 to determine if i is a factor. The significance of checking factors is that if n can be divided by i, then we can achieve n 'A's by first achieving i 'A's and then copying and pasting the i 'A's group (n/i) times (which needs i operations).

If a factor is found, the function calls itself recursively with the new target n // i, which represents the subproblem of reaching i 'A's. This recursive call adds the cost of i operations to the result (dfs(n // i) + i). We want the minimum number of operations, so we calculate and store the minimum (ans = min(ans, dfs(n // i) + i)).

The while loop ensures that we're only iterating up to the square root of n. This is an optimization because if n is not prime, it must have a factor less than or equal to its square root, thus we don't need to check beyond that.

Python's @cache decorator is used on the dfs function to memoize its results. This means that the results of the dfs calculations for each unique input are stored, so if the same value of n is passed to the function again, it doesn't compute it but retrieves the result from the cache. This significantly reduces the number of calculations and the time complexity of the algorithm, as it prevents us from recomputing the minimum steps for values we've already solved.

After defining the dfs function with memoization, the main function minSteps directly calls and returns the result of dfs(n), which computes the minimum number of steps needed to reach n 'A's on the notepad.

In summary, the solution is recursive, uses memoization for optimization, and leverages the mathematical insight that the number of steps for n 'A's is linked to the factors of n.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example using n = 8 'A's.

We start with one 'A' on the notepad. We need to reach exactly 8 'A's. We look for factors of 8, which are 2 and 4 (excluding 8 itself because we need to perform at least one copy and paste).

Here is a step-by-step walk through using the factor of 4:

Initial State: Notepad content is 'A' (operation count: 0)
Step 1: Copy All (operation count: 1)
Step 2: Paste (operation count: 2) - Notepad content is 'AA'
Step 3: Paste (operation count: 3) - Notepad content is 'AAA'
Step 4: Paste (operation count: 4) - Notepad content is 'AAAA'

Now, we have 'AAAA' on the notepad. The factor 4 is reached with 4 operations. Next:

Step 5: Copy All (operation count: 5)
Step 6: Paste (operation count: 6) - Notepad content is 'AAAAAAAA'

In this example, we needed a total of 6 operations to get to 8 'A's. We created 4 'A's in 4 operations and then doubled that with one extra copy and one paste.

We could use the other factor, which is 2, to achieve our goal:

Initial State: Notepad content is 'A' (operation count: 0)
Step 1: Copy All (operation count: 1)
Step 2: Paste (operation count: 2) - Notepad content is 'AA'

With the 'AA' ready:

Step 3: Copy All (operation count: 3)
Step 4: Paste (operation count: 4) - Notepad content is 'AAAA'
Step 5: Copy All (operation count: 5)
Step 6: Paste (operation count: 6) - Notepad content is 'AAAAAAAA'

The factor 2 also took 6 operations, so in this case, both factors provide the same result.

The recursive function dfs would calculate the number of steps for getting 'A' in quantities of factors of 8 and would recursively use the same logic for the factors themselves. @cache would ensure that the calculation for each amount of 'A's is done only once, even if needed multiple times throughout the recursion.

For this example, the minimum number of operations that dfs would report is 6, which matches our manual calculation.

Realizing that the factors of n are critical to finding the solution, we can see that as n gets larger or is a prime number, the number of operations needed will increase accordingly, and the algorithm efficiently finds the optimal set of operations needed for any n.

Solution Implementation

1class Solution:
2    def minSteps(self, n: int) -> int:
3        from functools import lru_cache
4
5        @lru_cache(maxsize=None)  # Use LRU cache to memoize the results of subproblems
6        def dfs(current):
7            # Base case: If the current number is 1, no steps are needed
8            if current == 1:
9                return 0
10
11            # Initialize ans with the maximum possible steps needed (which is n)
12            ans = current
13
14            # Iterate over possible divisors to find the minimum steps
15            divisor = 2
16            while divisor * divisor <= current:
17                # If current is divisible by divisor, then it can be obtained by
18                # adding the divisor to itself (n / divisor) times
19                if current % divisor == 0:
20                    # Compute the minimum steps recursively for the quotient and
21                    # add the number of steps needed for the current divisor
22                    ans = min(ans, dfs(current // divisor) + divisor)
23                divisor += 1
24
25            # In case n is a prime number, the answer would be n itself
26            return ans
27
28        # Call the recursive function with the initial value
29        return dfs(n)
30
31# Example usage:
32# s = Solution()
33# print(s.minSteps(10))  # Output would be 7
34

1class Solution {
2    // This method calculates the minimum number of steps to get 'n' 'A's on the notepad
3    // starting with only one 'A'. It involves a series of copy-all and paste operations.
4    public int minSteps(int n) {
5        // Initialize the result to store the minimum number of steps
6        int steps = 0;
7        // Start dividing 'n' from factor 2 onwards, as 1 wouldn't change the number
8        for (int i = 2; n > 1; ++i) {
9            // While 'n' is divisible by 'i', keep dividing it and add 'i' to the result.
10            // This is because, in terms of operations, if 'n' is divisible by 'i',
11            // it means we can get to 'n' by doing 'i' operations (copy, paste 'i'-1 times) that many times.
12            while (n % i == 0) {
13                steps += i; // Add the factor to the total steps
14                n /= i;     // Divide 'n' by the current factor 'i'
15            }
16        }
17        // Once 'n' is reduced to 1, we have found the minimum steps and return it
18        return steps;
19    }
20}
21

1class Solution {
2public:
3    // A memoization table to store results of subproblems
4    vector<int> memo;
5
6    // Main function to compute the minimum steps required to get 'n' 'A's on the notepad
7    int minSteps(int n) {
8        // Initialize the memoization table with '-1', to indicate that no subproblem is solved yet
9        memo.assign(n + 1, -1);
10
11        // Call the recursive depth-first-search function to compute the answer
12        return dfs(n);
13    }
14
15    // Helper function to perform the depth-first search
16    int dfs(int n) {
17        // If only one 'A' is needed, 0 steps are required
18        if (n == 1) return 0;
19
20        // If the result has already been computed, return it instead of recomputing
21        if (memo[n] != -1) return memo[n];
22
23        // Initialize the answer with the maximum value, which is 'n' (copying 'A' one by one)
24        int ans = n;
25
26        // Try to find the minimal steps by finding divisors of 'n'
27        for (int i = 2; i * i <= n; ++i) {
28            // If 'i' is a divisor of 'n'
29            if (n % i == 0) {
30                // Recursively solve for the smaller problem 'n / i' and add 'i' steps
31                // (the steps to paste 'A's 'i-1' times after copying once)
32                ans = min(ans, dfs(n / i) + i);
33            }
34        }
35
36        // Save the computed answer to the memoization table
37        memo[n] = ans;
38
39        // Return the minimum number of steps calculated
40        return ans;
41    }
42};
43

1// A memoization table to store results of subproblems
2const memo: number[] = [];
3
4// Function to compute the minimum steps required to get 'n' 'A's on the notepad
5const minSteps = (n: number): number => {
6    // Initialize the memoization table with '-1' to indicate that no subproblem is solved yet
7    memo.fill(-1, 0, n + 1);
8
9    // Call the recursive depth-first search function to compute the answer
10    return dfs(n);
11};
12
13// Helper function to perform the depth-first search
14const dfs = (n: number): number => {
15    // If only one 'A' is needed, 0 steps are required
16    if (n === 1) return 0;
17
18    // If the result has already been computed, return it instead of recomputing
19    if (memo[n] !== -1) return memo[n];
20
21    // Initialize the answer with the maximum value, which is copying 'A' one by one
22    let ans = n;
23
24    // Try to find the minimal steps by finding divisors of 'n'
25    for (let i = 2; i * i <= n; ++i) {
26        // If 'i' is a divisor of 'n'
27        if (n % i === 0) {
28            // Recursively solve for the smaller problem 'n / i' and add 'i' steps (the steps to paste 'A's 'i - 1' times after copying once)
29            ans = Math.min(ans, dfs(n / i) + i);
30        }
31    }
32
33    // Save the computed answer to the memoization table
34    memo[n] = ans;
35
36    // Return the minimum number of steps calculated
37    return ans;
38};
39
40// Utility function to fill an array from the `start` index up to but not including the `end` index with the `value`.
41const fill = (arr: number[], value: number, start: number, end: number): void => {
42    for (let i = start; i < end; ++i) {
43        arr[i] = value;
44    }
45};
46
47// Example override of the initial fill function to provide the specific functionality needed.
48memo.fill = (value: number, start?: number, end?: number): number[] => {
49    fill(memo, value, start || 0, end || memo.length);
50    return memo;
51};
52

Time and Space Complexity

Time Complexity

The time complexity of the minSteps function primarily is from the dfs function that it calls. The dfs function is a depth-first search approach that looks for the minimum number of operations to get n characters by only using copy and paste operations.

For each n, the function iterates from 2 to the square root of n to find factors, and at each factor i, it recursively calculates dfs(n // i) + i, which adds the operations needed to obtain n from n // i plus the operations to get i characters in the first place.

The worst-case time complexity is hard to evaluate directly because of the recursive nature and the caching of intermediate results. However, a factor that influences the time complexity is the number of divisors of n. In the worst case, these divisors form a tree, where we explore n // i for each factor i of n.

Since the largest prime less than m can be O(m/log(m)) and the prime factorization of n can have at most log(n) terms, the upper bound on the time complexity can be seen as O((n / log(n)) * log(n)), which simplifies to O(n). The use of caching/memoization via the @cache decorator avoids re-calculating the number of steps for the same n in the recursive calls.

Space Complexity

The space complexity is mainly due to two contributors - the system call stack due to recursion and the space used for caching the results. In the worst case, the recursion depth is equal to the number of distinct prime factors which are O(log(n)). Hence, O(log(n)) space is used in the call stack.

Additionally, the @cache decorator potentially stores the result for every unique argument to dfs between 1 and n, therefore, taking up O(n) space in the worst case, if very little overlapping occurs in the computations. As a result, the overall space complexity of the algorithm is O(n + log(n)), which simplifies to O(n) when we drop the lower-order term.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know