Solution with running time independent of "amount"


  • 0
    R

    The following solution's running time is independent of amount and depends only coins:

    def gcd(a,b):
                if b > a:
                    return gcd(b,a)
                elif b == 0:
                    return a
                else:
                    return gcd(b, a%b)
            
    lcm = lambda a,b : a*b//gcd(a,b)
    
    class Solution:
        def coinChange(self, coins, amount):
            """
            :type coins: List[int]
            :type amount: int
            :rtype: int
            """
            
            # Checking Trivial Cases
            if amount == 0:
                return 0
            if len(coins) == 0:
                return -1
            
            # Find the LCM of the coin sizes
            l = 1
            for c in coins:
                l = lcm(l,c)
            
            # Reduce to a case where amount is less than LCM if needed
            if amount > l:
                redCount = self.coinChange( coins, amount % l )
                if redCount == -1:
                    return -1
                else:
                    return redCount + (amount // l)*(l//max(coins))
            
            # Dynamic Programming Part
            count = [0] * (amount + 1)
            for n in range(1, amount + 1):
                prev = [ count[n-c] for c in coins if c <= n and count[n-c] != -1 ]
                if len(prev) == 0:
                    count[n] = -1
                else:
                    count[n] = min(prev) + 1
            
            return count[amount]
    

    The "dynamic programming" part only needs a number of steps equal to the least common multiple of the coin sizes rather than a number of steps proportional to amount. Thus running time and space is proportional to the least common multiple of the coin sizes. This allows for handling cases such as coins=[1] and amount=10**10.


Log in to reply
 

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