# Python, Straightforward with Explanation

• We can break the total sequence of operations into groups that take the form "[copy][some number of pastes]" In K operations of this group, the length of the string is multiplied by K.

Now, suppose N can be written as N = d_1 * d_2 * ... * d_k. By the above reasoning, N "A"s can be written on the tape in d_1 + d_2 + ... + d_k operations. If any of the d_i are composite, say d_i = p*q (with p>1, q>1), then we could write it in p + q instead of p*q operations by breaking up this divisor.

For example, if we make 15 with 15 operations, we could instead make it with 3 operations to get AAA then another 5 operations. Also, we should justify that p+q <= p*q (because (p-1)(q-1) is positive), so we indeed do get savings by breaking up this product.

def minSteps(self, n):
def factors(n):
d = 2
while d * d <= n:
while n % d == 0:
n /= d
yield d
d += 1
if n > 1:
yield n

return sum(factors(n))

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.