# 6-7 lines, 2 ways

• I'm surprised that out of all solutions so far, only yular used the coins for the outer loop. Everybody else used the amount for the outer loop. Making coins the outer loop saves the extra "if" and quite some time. Here's a comparison of both ways.

Solution 1, `coins` outer loop, average 92ms

``````int coinChange(vector<int>& coins, int amount) {
vector<int> need(amount+1, amount+1);
need[0] = 0;
for (int c : coins)
for (int a=c; a<=amount; a++)
need[a] = min(need[a], need[a-c] + 1);
return need.back() > amount ? -1 : need.back();
}
``````

Solution 2, `amount` outer loop, average 180ms

``````int coinChange(vector<int>& coins, int amount) {
vector<int> need(amount+1, amount+1);
need[0] = 0;
for (int a=1; a<=amount; a++)
for (int c : coins)
if (c <= a)
need[a] = min(need[a], need[a-c] + 1);
return need.back() > amount ? -1 : need.back();
}``````

• @StefanPochmann , can you explain why execution time is different? Tested the same thing and got similar results.

• Could you please translate the codes into python? Really appreciates. Thanks.

• @sbdust

``````def coinChange(self, coins, amount):
# need = [amount + 1] * (amount + 1)
# need[0] = 0

need = [0] + [amount + 1] * amount

for c in coins:
for a in xrange(c, amount + 1):
need[a] = min(need[a], need[a - c] + 1)

return -1 if need[-1] > amount else need[-1]``````

• @pankesh Easy to combine the first two lines in Python...

• @broccoli I edited the code. Please see the comments now. Sorry for confusion.

• Thanks to you guys.

• @StefanPochmann
I found there is little difference in Python for these two solution.
The first 1600ms+ and the second 1500ms+

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