# Solution with running time independent of "amount"

• 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`.

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