Give Exact Change at a Ticket Kiosk

Easy15–20 min

Topics

GreedySimulationCounting

Companies

AmazonZomatoSwiggy

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.

Test Case 1:

Input:payments = [4, 4, 4, 8, 8, 20, 8]

Output:true

Explanation:Three 4s are collected. Each 8 needs a 4 back; the 20 needs 16 back, paid as two 8s. The last 8 takes the remaining 4.

Test Case 2:

Input:payments = [8]

Output:false

Explanation:The first customer pays 8 for a 4 ticket and needs a 4 back, but the kiosk has nothing.

Test Case 3:

Input:payments = [4, 4, 4, 4, 20]

Output:true

Explanation:With no 8s available, the 20 note is given 16 change as four 4s.

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

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Try Every Way to Give the Change

Brute

Serve the customers in order while tracking how many 4-notes and 8-notes the kiosk holds. A customer paying 4 needs no change; paying 8 needs one 4 back. A customer paying 20 needs 16 back, which can be made three ways — two 8s, one 8 and two 4s, or four 4s — so try each way the kiosk can actually afford and recurse on the rest; if none of them lets the remaining customers finish, this customer cannot be served. This is guaranteed to find a way if any exists, but each 20 can branch three ways.

TimeO(3ᵏ) for k customers paying 20

SpaceO(n)

Java

Try it out

class Solution {
    public boolean canGiveChange(int[] payments) {
        return serve(payments, 0, 0, 0);
    }

    private boolean serve(int[] payments, int index, int fours, int eights) {
        if (index == payments.length) return true;
        int pay = payments[index];
        if (pay == 4) return serve(payments, index + 1, fours + 1, eights);
        if (pay == 8) return fours >= 1 && serve(payments, index + 1, fours - 1, eights + 1);
        for (int useEights = 0; useEights <= 2; useEights++) {
            int needFours = (16 - 8 * useEights) / 4;
            if (useEights <= eights && needFours <= fours
                    && serve(payments, index + 1, fours - needFours, eights - useEights)) return true;
        }
        return false;
    }
}

Optimal — Count Notes and Always Prefer the 8s

Optimal

Keep just two counters, fours and eights. For a 20 the change of 16 should be made with as many 8s as possible: an 8-note can only ever help as change for a 20-payer, while 4-notes are useful for both 8-payers and 20-payers, so the 4-notes are the scarcer resource and should be saved for later. Concretely: pay a 20 with two 8s if possible; otherwise with one 8 and two 4s; otherwise with four 4s; otherwise fail. A single pass, no recursion and no backtracking.

TimeO(n)

SpaceO(1)