Change at the chai stall
Give change for ₹20 using a ₹10 and a ₹5 rather than three ₹5 to preserve flexibility. About 8 minutes.
The ₹5 chai stall
Each cup of chai costs ₹5. Customers come one at a time and pay with a ₹5, ₹10 or ₹20 note. You start the day with no money, and you must give exact change to each customer immediately.
So the notes you collect from earlier customers are the only change you have for later ones.
- ₹5
- 3
- ₹10
- 0
Three ₹5s: no change needed. Keep them.
Greedy note prioritization
When a customer pays ₹20, you return ₹15. You could give three ₹5 notes, or one ₹10 and one ₹5. Always give the ₹10 and ₹5 if you can. A ₹5 is much more flexible, because it can change a ₹10 later, whereas a ₹10 is useless when you need to change a ₹10.
five, ten = 0, 0
for b in bills:
if b == 5:
five += 1
elif b == 10:
if five == 0:
return False
five -= 1
ten += 1
else:
if ten > 0 and five > 0:
ten -= 1
five -= 1
elif five >= 3:
five -= 3
else:
return False
return TrueWhy prefer giving ₹10 + ₹5 instead of three ₹5 when changing ₹20?
- ABecause ₹5 are needed to change future ₹10, but ₹10 cannot
- BBecause handing over 2 notes is faster than 3 notes
Show the answer
Because ₹5 are needed to change future ₹10, but ₹10 cannot. A ₹10 cannot change another ₹10, so keeping ₹5 gives maximum future flexibility.
Change at the chai stall
A chai stall sells every cup for ₹5 and opens with an empty cash box. Customers arrive one by one in the order given by bills, each buying one cup and paying with a ₹5 coin, a ₹10 note or a ₹20 note. The stall must hand back exact change straight away, using only money already in the box. Return true if every customer gets correct change, or false as soon as one can't.
bills = [5, 5, 5, 10, 20] → true
1 ≤ bills.length ≤ 100,000 · bills[i] is either 5, 10, or 20