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: no change needed: keep the note.

₹10: needs ₹5 back: keep the ₹10, give one ₹5.

₹20: needs ₹15 back: prefer one ₹10 and one ₹5.

Chai at ₹5 · bills = [5, 5, 5, 10, 20]

customer

₹5: 3
₹10: 0

Three ₹5s: no change needed. Keep them.

Move 1 of 4

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.

Greedy choice: spend one ₹10 and one ₹5 first.

Fallback: only spend three ₹5 notes if you have no ₹10.

In code

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 True