Python, Straightforward with Explanation


  • 3

    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))
    

Log in to reply
 

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