This article includes the code implementation in Python, a detailed explanation, and the complexity analysis for LeetCode 650. 2 Keys Keyboard. Please hit the like button if you find this article is helpful. I will keep writing LeetCode solutions.
In each step, we need to decide whether to run the Copy All or the Paste operation. To achieve the minimum steps, we should greedily run the Copy All operation as much as we can.
When can we greedily run the Copy All operation? We just need to check whether the remaining length of
'A' to be pasted can be divided by the length of the newly copied
'A' after the current Paste operation.
Input: n = 4 Output: 4
Explanation: Initially, we have one character
In step 1, we can only use the Copy All operation. The current length is 1.
In step 2, we can only use the Paste operation. The current length is 2.
In step 3, now we need to decide if using the Copy All operation is okay. If we use the Copy All operation here, the new copied length becomes 2. The remaining length to be pasted is 4 - 2 = 2 which can be dived by the new copied length 2. Hence, we can greedily run the Copy All operation.
In step 4, we use the Paste operation. The current length is 4.
class Solution: def minSteps(self, n: int) -> int: step, curLen, copyLen = 0, 1, 1 while curLen < n: # The length of the potential copy nextCopyLen = curLen + copyLen curLen += copyLen # Run the Paste operation if (n - nextCopyLen) % nextCopyLen: step += 1 else: # Run the Copy All and the Paste Operation copyLen = nextCopyLen step += 2 return step
O(n) time in the worst case since we might need to run the Paste operation with copied length 1.
O(log(n)) time in the average case since we can double the copied length with each Copy All operation.
O(1) space since we only use some additional variables.