Python DP O(n) solution beats 99% solutions


  • 0
    H
    class Solution(object):
        def minSteps(self, n):
            copy = 1
            steps = 1
            for i in range(2, n + 1):
                if n % i == 0 and i % copy == 0:
                    steps += i / copy
                    copy = i
            return steps -1
    

    Basically we will get minimum paste count only if we paste the maximum value in the final step. The maximum value that we can paste in the final step will be a factor of n. So essentially we pick a maximum factor of n, which we can make from existing number count in copy step. Hence I do n % i == 0 and i % copy. After do maximum number of past's i.e i/copy. We update the copy to the next bigger factor.


Log in to reply
 

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