In the mystical village of Coinholt, you stand behind the counter of your bakery, arranging a fresh batch of pastries. The door creaks open, and in walks Denara, a skilled merchant with a keen eye for quality goods. After a quick meal, she slides a shimmering coin across the counter, representing a value of 100 units.
You smile, taking the coin, and glance at the total cost of the meal: 88 units. That means you need to return 12 units in change.
Denara holds out her hand expectantly. "Just give me the fewest coins," she says with a smile. "My pouch is already full, and I don't want to risk losing them on the road."
You know you have a few options. "We have Lumis (worth 10 units), Viras (worth 5 units), and Zenth (worth 2 units) available for change."
You quickly calculate the possibilities in your head:
"The best choice is two coins: one Lumis and one Zenth," you say, handing her the change.
Denara smiles, clearly impressed. "As always, you've got it right."
Determine the fewest number of coins to give a customer so that the sum of their values equals the correct amount of change.
Sign up to Exercism to learn and master AWK with 79 exercises, and real human mentoring, all for free.