Greedy coin change
A parking kiosk hands change back out of the hopper it has on hand. coin_cents[i] is what one coin of kind i is worth in cents, always at least one cent, and hopper_counts[i] is how many of that kind the hopper holds. The values are distinct and they arrive in no particular order. The kiosk pays greedily: it repeatedly takes the largest coin it still holds that is worth no more than the amount still owed, hands it over, and carries on until nothing is owed. It never takes a coin back, so it can stall on an amount that some other mix of coins would have covered. amount_cents is never negative. Return how many of each kind it paid, in the order coin_cents gives them. Return an empty list when the kiosk stalls with money still owed. Owing nothing is not a stall, so it pays a zero of every kind.
kiosk_change_payout(coin_cents: list[int], hopper_counts: list[int], amount_cents: int) → list[int][[25,10,5],[2,1,3],40]out[1,1,1][[25,10],[1,3],30]out[][[25,10,5],[4,4,4],0]out[0,0,0]State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[[25,10,5],[2,1,3],40][1,1,1]not run yetsample[[25,10],[1,3],30][]not run yetsample[[25,10,5],[4,4,4],0][0,0,0]not run yetsample