# Wei-Lin Cheng  # 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.