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.

Intuition

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.

Example

Input: n = 4
Output: 4

Explanation: Initially, we have one character 'A'. 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.

Solution

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

Complexity Analysis

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.