You're using a Greedy algorithm, which works for canonical coin values, e.g. [1, 5, 10, 25], and as it happens, it also works for all the test cases you've chosen.
Try coins = [1, 20, 25] and amount = 40 and greedy fails hard. You're taking the highest denomination first, so it takes 25, then can’t make 15 with {20, 25}, so falls back to fifteen 1s = sixteen coins. The optimal is two 20s = two coins.
To make this work for arbitrary coin denominations, you need dynamic programming.
On the assumption that late is better than never, here is my contribution to the conversation.
I could not see the merit of the solutions you recommended. 3 coins = 3 iterations. I did not see recursion / memory in the solution, perhaps I am missing something. But I read this page during 'coding time' just before midnight, so gave it a stab.
In python :
def countcoins(coins , targetsum):
....'''
....Returns the minimum number of coins required to make the given value sum
....Todo : Defence against unexpected input & hints
....:param coins: The coins to be considered
....:param targetsum: The sum to make with specified coins
....'''
....countcount = 0
....running_total = targetsum
....coins.sort(reverse=True) #so we consider them highest coin first
....for coin in coins:
........countcount += int(running_total//coin)
........running_total = running_total%coin
........if not running_total:
............break
....if running_total == 0:
........return countcount
....else:
........return -1
----------------
running_total = targetsum is about readability
if not running_total is about ...why not. == 0 is the same.
@psiro -
Did you look at the review post for this challenge: https://paulepps.substack.com/p/review-and-feedback-coin-change-and
You're using a Greedy algorithm, which works for canonical coin values, e.g. [1, 5, 10, 25], and as it happens, it also works for all the test cases you've chosen.
Try coins = [1, 20, 25] and amount = 40 and greedy fails hard. You're taking the highest denomination first, so it takes 25, then can’t make 15 with {20, 25}, so falls back to fifteen 1s = sixteen coins. The optimal is two 20s = two coins.
To make this work for arbitrary coin denominations, you need dynamic programming.
Oh dear, I completely missed that - I'll try again. Thanks for the tip.
I must have got side-tracked by the canonical nature of coins in the real world.
If anything, I have developed an appreciation of the coins available in the real world.
Great page.
On the assumption that late is better than never, here is my contribution to the conversation.
I could not see the merit of the solutions you recommended. 3 coins = 3 iterations. I did not see recursion / memory in the solution, perhaps I am missing something. But I read this page during 'coding time' just before midnight, so gave it a stab.
In python :
def countcoins(coins , targetsum):
....'''
....Returns the minimum number of coins required to make the given value sum
....Todo : Defence against unexpected input & hints
....:param coins: The coins to be considered
....:param targetsum: The sum to make with specified coins
....'''
....countcount = 0
....running_total = targetsum
....coins.sort(reverse=True) #so we consider them highest coin first
....for coin in coins:
........countcount += int(running_total//coin)
........running_total = running_total%coin
........if not running_total:
............break
....if running_total == 0:
........return countcount
....else:
........return -1
----------------
running_total = targetsum is about readability
if not running_total is about ...why not. == 0 is the same.
----------------
Usage
print(countcoins([25, 10, 5],30))
print(countcoins([9, 6, 5, 1],19))
print(countcoins([5, 1],0))
print(countcoins([4, 6, 2],5))