Today’s challenge
Build the solution
Write a function called make_change(amount, coins) for a cash drawer.
Return contract: A dictionary with possible (boolean), coins (records with value and count), and count (total coins, or null when impossible). Impossible payments have an empty coins list.
Input bounds: amount 0–300; 0–6 denominations; values 1–300; available counts 0–12. The input denomination order is arbitrary.
Keep the supplied driver below your implementation. It reads one JSON object and prints your return value as JSON. The driver may also probe the behaviour described above; those probe fields are part of the test input.
- Each coin record contains a unique positive value and its available count. Pay the exact amount without exceeding any count.
- Choose a solution using the fewest coins. If several solutions use the same number, favor the one with more of the highest-value coin; continue comparing lower denominations until the tie is broken.
- Report only denominations actually used, in descending value order. For zero amount, return a successful empty payment.
The Twist: The largest coin may strand the remaining amount. Your algorithm must find a valid alternative and prove it is the best under both ordering rules.
Sample
Input
{"amount":6,"coins":[{"count":1,"value":4},{"count":2,"value":3},{"count":2,"value":1}]}Expected output
{"coins":[{"count":2,"value":3}],"count":2,"possible":true}