Loading page…
Practice problem · easy
You help a friend run a lemonade stand. Every cup costs 5 units. Customers line up and each buys one cup, paying with a note worth 5, 10 or 20 units. Your friend starts the day with no money, and can give change only from the notes received so far.
Customers are served in line order.
Your team lead asks: "Can every customer get the right change?"
Write can_give_change(payments).
payments[i] is the note the customer at position i pays with. It is 5, 10 or 20.true if every customer can be given the right change, and false if some customer cannot.Input: payments = [5, 5, 5, 10, 20]
Output: trueKeep a count of 5-notes and 10-notes in hand. A 10 needs one 5 back. A 20 needs a 10 and a 5 if possible, and otherwise three 5s.
| Customer | Pays | Change given | 5-notes | 10-notes |
|---|---|---|---|---|
| start | 0 | 0 | ||
| 1 | 5 | none | 1 | 0 |
| 2 | 5 | none | 2 | 0 |
| 3 | 5 | none | 3 | 0 |
| 4 | 10 | one 5 | 2 | 1 |
| 5 | 20 | a 10 and a 5 | 1 | 0 |
Everyone got change, so the answer is true.
Input: payments = [5, 5, 10, 10, 20]
Output: falseAfter the first four customers there are no 5-notes and two 10-notes. The last customer needs 15 back, and 10 and 10 is not 15.
Input: payments = [10, 10]
Output: falseThe first customer pays 10 and needs a 5 back. Nothing has been received yet, so there is none.
0 ≤ len(payments) ≤ 100,000There can be 100,000 customers. Every 20 can be paid out in two ways. Trying both ways for each 20 gives 2 to the power of 1000 combinations for only 1,000 twenties, which is hopeless. A pass that makes one fixed choice for every customer costs 100,000 steps.
can_give_change · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.