4 Keys Keyboard
MicrosoftThe problem
Imagine you have a special keyboard with the following keys:
-
A: Print one 'A' on the screen.
-
Ctrl-A: Select the whole screen.
-
Ctrl-C: Copy selection to buffer.
-
Ctrl-V: Print buffer on screen appending it after what has already been printed.
Given an integer n, return the maximum number of 'A' you can print on the screen with at most n presses on the keys.
Input: n = 3 Output: 3 Explanation: We can at most get 3 A's on screen by pressing the following key sequence: A, A, A
Input: n = 7 Output: 9 Explanation: We can at most get 9 A's on screen by pressing following key sequence: A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V
input: n = 6
- 1 <= n <= 50
cpp
class Solution {
public:
int maxA(int n) {
// Your code goes here
}
};java
class Solution {
public int maxA(int n) {
// Your code goes here
}
}python
class Solution(object):
def maxA(self, n):
"""
:type n: int
:rtype: int
"""
# Your code goes herejavascript
/**
* @param {number} n
* @return {number}
*/
var maxA = function(n) {
// Your code goes here
};csharp
public class Solution {
public int maxA(int n) {
// Your code goes here
}
}go
func maxA(n int) int {
}Stuck? Show a way to structure it+
- 01Define dp[0]=0 and small-n behavior
- 02Use the direct typing transition
- 03Try every earlier breakpoint for copy-paste blocks
- 04Return dp[n] and explain the multiplier
Reference answer
Then expect these follow-ups
Can you reduce the search range?
Tests: follow-up reasoning
Why is a final copy-paste block sufficient?
Tests: correctness reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question