Give Exact Change at a Ticket Kiosk
Implement canGiveChange
A parking-ticket kiosk sells tickets that each cost 4. Customers line up and each pays with exactly one note: a 4 (no change needed), an 8 (change of 4) or a 20 (change of 16). The kiosk starts empty and can only give change using notes it has already collected from earlier customers. Decide whether every customer can be given exact change.
A 20 can be changed in several ways (two 8s, an 8 and two 4s, or four 4s), and trying all of them can branch a lot. A greedy rule removes the branching: 4-notes are useful for every kind of customer, so prefer paying 20s with 8-notes and save the 4s.
Example 1:
Input: payments = [4,4,4,8,8,20,8]
Output: true
Example 2:
Input: payments = [8]
Output: false
Example 3:
Input: payments = [4,4,4,4,20]
Output: true
+ 9 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ payments.length ≤ 14 - ●
Every ticket costs 4. Each customer pays with exactly one note, and every payments[i] is 4, 8 or 20 - ●
The kiosk starts with no notes at all and can only give change using notes it has already collected from earlier customers (a 20 note is never used as change) - ●
Customers are served in order. Return true if every customer can be given exact change, otherwise false
payments =