Ferry Fare Change
You run the ticket window for a small river ferry. A crossing costs $5. Passengers pay with a single $5, $10 or $20 bill, and you must hand back exact change on the spot.
Your cash box starts empty in the morning. The only money you can give as change is the bills earlier passengers paid with. You know the order of today's passengers and the bill each will hand you. Can you serve all of them?
Your task
Write canGiveChange(bills). bills[i] is the bill the i-th passenger pays with, in queue order. Each passenger buys exactly one $5 ticket. Return true if you can give every passenger correct change, and false as soon as one passenger cannot get it.
Bills you receive go into the cash box and can be used as change for later passengers. An empty queue returns true.
canGiveChange(bills: int[]) → bool
Examples
bills = [5, 5, 10, 20]
true
The first two passengers pay exactly: the box holds two $5. The third pays $10 and gets one $5 back: the box holds one $5 and one $10. The fourth pays $20 and needs $15: give the $10 and the $5. Everyone is served.
bills = [5, 10, 10]
false
After the first two passengers, the box holds one $10 and no $5. The third passenger needs $5 back, and a $10 bill cannot be split. Fail.
Constraints
- 0 ≤ bills.length ≤ 100,000
- bills[i] is 5, 10 or 20
Start with brute force
For every $20 passenger there are up to two ways to make change. You could try both ways for each of them and see if any sequence of choices serves the whole queue. With k passengers paying $20 that is up to 2k sequences, so 40 such passengers already means about a trillion tries.
The branching is wasted work: one of the two choices is never worse than the other, so you never need to try both.
Hints
0 of 4 shown- Hint 1
A $5 and a $10 are not equally useful as change. Which passengers can you serve with a $10 in the box, and which need a $5?
- Hint 2
Every $10 passenger needs a $5 back. A $20 passenger needs $15, which is either $10 + $5 or $5 + $5 + $5. The $10 is only ever useful in that first combination.
- Hint 3
When a $20 arrives and you could pay either way, which choice leaves you with more $5 bills for the passengers still to come?
- Hint 4
Count $5 and $10 bills in the box (a $20 is never useful as change). For $10, give back a $5. For $20, prefer $10 + $5, and use three $5 bills only if you have no $10. Return false the moment a payment is impossible.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
A $5 bill can help every future passenger. A $10 bill can only help a $20 passenger. So when you have a choice, spend the less flexible bill and keep the $5s.
Trace [5, 5, 5, 5, 10, 20, 10], counting (fives, tens):
- Four $5 passengers: (4, 0).
- $10: give a $5 back. (3, 1).
- $20: you could give $10 + $5 or three $5s. Give $10 + $5. (2, 0).
- $10: give a $5 back. (1, 1). Everyone served:
true.
Had you paid the $20 with three $5s, the box would hold (0, 1) and the last passenger could not get their $5. Same total money in the box, but the wrong shape.
function canGiveChange(bills) {
let fives = 0, tens = 0; // $20 bills are never given as change
for (const bill of bills) {
if (bill === 5) {
fives++;
} else if (bill === 10) {
if (fives === 0) return false;
fives--; tens++;
} else if (tens > 0 && fives > 0) {
tens--; fives--; // spend the less useful $10 first
} else if (fives >= 3) {
fives -= 3;
} else {
return false;
}
}
return true;
}def can_give_change(bills):
fives = tens = 0 # $20 bills are never given as change
for bill in bills:
if bill == 5:
fives += 1
elif bill == 10:
if fives == 0:
return False
fives -= 1
tens += 1
elif tens > 0 and fives > 0:
tens -= 1 # spend the less useful $10 first
fives -= 1
elif fives >= 3:
fives -= 3
else:
return False
return TrueRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.