Easy · Greedy Change Choice
Understand → Visualise → Practice.
Each lemonade costs ₹5 and customers pay with ₹5, ₹10 or ₹20 in order. Return whether exact change is always possible.
Keep a count of ₹5 and ₹10 notes. A ₹20 can be changed with 10 + 5 or with 5 + 5 + 5; use the ₹10 first, because ₹5 notes are needed for every kind of change.
Count the ₹5 and ₹10 notes in the till.
₹5: keep it. ₹10: give back a ₹5. ₹20: give ₹10 + ₹5 if possible, otherwise three ₹5s.
If you ever lack the notes for change, return false; otherwise true.
O(n) time and O(1) space.
Paying ₹15 change with three ₹5s while a ₹10 is available wastes the notes you need later.
Read the full guide first: Greedy Algorithms and Interval Patterns.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.