The vending machine had the coins. Greedy still got stuck.

transcript

20 rupees in. 14 rupee biscuits. The machine owes you 6. It has the coins. And it still gets stuck.

Inside the box: one 5 rupee coin. And three 2 rupee coins. 6 rupees to give back. Easy, right?

The textbook move is greedy. Largest coin first. Take the 5. Now it needs 1 more rupee. There isn't one. Stuck. Fail, or short-change you. But 2 plus 2 plus 2 was right there.

With unlimited Indian coins, greedy is always optimal. A real machine has a limited box. Greedy can fail. So search the coins actually present. A small bounded search. It returns the fewest coins. Or none at all.

Machine one: change is three 2 rupee coins. Biscuits drop. Machine two holds only a 5. No way to make 6. So it refuses. Exact amount only. Before anything drops.

Count the coins actually there. Even the customer's own. And work out change before you dispense. Never after.

Full breakdown in the lecture.