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.
| Register | Usage | Type | Description |
|---|---|---|---|
$a0 |
input | integer | number of input coins |
$a1 |
input | integer | target |
$a2 |
input/output | address | overwritable array of coin words |
$v0 |
output | integer | number of output coins, -1 if input invalid |
$t0-9 |
temporary | any | used for temporary storage |
Sign up to Exercism to learn and master MIPS Assembly with 70 exercises, and real human mentoring, all for free.