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.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___ in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
121public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
161function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16Solution 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.
What's the output of running the following function using input 56?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
271private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
301const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30Example 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
341class 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}
211class 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};
431// 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};
52Which data structure is used to implement priority queue?
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.
In a binary min heap, the maximum element can be found in:
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.