Skip to content

Instantly share code, notes, and snippets.

@vlad-bezden
Created October 17, 2021 20:13
Show Gist options
  • Save vlad-bezden/0be7d31d470a3866ed5dc391eebdcd14 to your computer and use it in GitHub Desktop.
Save vlad-bezden/0be7d31d470a3866ed5dc391eebdcd14 to your computer and use it in GitHub Desktop.
Change Making Problem. The minimum number of coins to get a certain amount of money.
from collections import Counter
from fractions import Fraction
penny = Fraction(1, 100)
nickel = Fraction(5, 100)
dime = Fraction(10, 100)
quarter = Fraction(25, 100)
usd = [penny, nickel, dime, quarter]
def change(amount, coins):
for coin in sorted(coins, reverse=True):
while coin <= amount:
amount -= coin
yield coin
amount = Fraction("1.42")
for coin, count in Counter(change(amount, usd)).items():
print(f"{count:>2} × ${float(coin):.2f}")
# Output
#
# 5 × $0.25
# 1 × $0.10
# 1 × $0.05
# 2 × $0.01
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment