Lemonade Change

EASY✓ CHIP-TIMEDLC #860 — FULL STATEMENT ↗

The drill: A lemonade stand charges $5 and starts with an empty till. Customers pay with $5, $10, or $20 bills in a fixed order — decide whether every one of them can get correct change from bills collected so far.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A line of customers pays for five-dollar lemonades one at a time, each handing over a five, a ten, or a twenty. Every purchase needs exact change back, drawn only from bills already collected earlier in the line.

The till starts empty, and bills accumulate strictly in the order customers pay — there's no reordering the line or peeking ahead. The moment any customer can't get correct change, the whole line of service fails.

The result is a single verdict: whether every customer in the given order walks away with correct change, using only bills that arrived before them.

EX 01

bills = [5, 5, 5, 5, 10, 20, 20]

→ false

TWO TWENTIES STRAND A LONE FIVE

EX 02

bills = [5, 5, 10, 20]

→ true

TEN-PLUS-FIVE CHANGE WORKS

EX 03

bills = [10, 5, 20]

→ false

OPENS WITH A TEN — NO CHANGE ON HAND

each payment is exactly $5, $10, or $20 — no other bill values appear
the till holds nothing at the start, only bills already collected count
customers are served strictly in the listed order, with no reordering
change must be exact — partial or overpaid change is not acceptable

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Checking every possible way to hand out change explores a branching tree of choices at each $20 — but two of the bills you could hand back are worth exchanging for. Which one is more valuable to keep on hand?

HINT 2 THE STRUCTURE

A $5 bill can cover change for a $10 OR a $20. A $10 bill can only ever cover change for a $20. Spending the less flexible bill first is never a mistake.

HINT 3 ONE STEP FROM THE ANSWER

Track running counts of fives and tens only — tens never help elsewhere. For a $20, use one ten plus one five if you have both; otherwise fall back to three fives; otherwise the till has failed.

COACH'S BOARD — THE PATTERN, STEP BY STEP

KEEP THE FIVES SCARCEPATTERN · GREEDYbills = [5, 5, 5, 10, 10, 20, 5, 20]

TILL — FIVES · TENS

fives → 0

tens → 0

STEP 1

Bills arrive in order 5, 5, 5, 10, 10, 20, 5, 20. The till starts with zero fives and zero tens.

STEP 1 / 10 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/lemonade-change.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five = ten = 0
        for bill in bills:
            if bill == 5:
                five += 1
            elif bill == 10:
                if five == 0:
                    return False
                five -= 1
                ten += 1
            else:
                if ten > 0 and five > 0:
                    ten -= 1
                    five -= 1
                elif five >= 3:
                    five -= 3
                else:
                    return False
        return True

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 20 LN

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        def backtrack(i: int, five: int, ten: int) -> bool:
            if i == len(bills):
                return True
            bill = bills[i]
            if bill == 5:
                return backtrack(i + 1, five + 1, ten)
            if bill == 10:
                if five == 0:
                    return False
                return backtrack(i + 1, five - 1, ten + 1)
            # bill == 20: try ten-plus-five first, then three fives
            if ten > 0 and five > 0:
                if backtrack(i + 1, five - 1, ten - 1):
                    return True
            if five >= 3:
                if backtrack(i + 1, five - 3, ten):
                    return True
            return False

        return backtrack(0, 0, 0)

TIME O(2^N)SPACE O(N)PYTHON · TRAINING PACE · 22 LN

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five == 0) {
                    return false;
                }
                five--;
                ten++;
            } else {
                if (ten > 0 && five > 0) {
                    ten--;
                    five--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 26 LN

class Solution {
    public boolean lemonadeChange(int[] bills) {
        return backtrack(bills, 0, 0, 0);
    }

    private boolean backtrack(int[] bills, int i, int five, int ten) {
        if (i == bills.length) {
            return true;
        }
        int bill = bills[i];
        if (bill == 5) {
            return backtrack(bills, i + 1, five + 1, ten);
        }
        if (bill == 10) {
            if (five == 0) {
                return false;
            }
            return backtrack(bills, i + 1, five - 1, ten + 1);
        }
        // bill == 20: try ten-plus-five first, then three fives
        if (ten > 0 && five > 0) {
            if (backtrack(bills, i + 1, five - 1, ten - 1)) {
                return true;
            }
        }
        if (five >= 3) {
            if (backtrack(bills, i + 1, five - 3, ten)) {
                return true;
            }
        }
        return false;
    }
}

TIME O(2^N)SPACE O(N)JAVA · TRAINING PACE · 33 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED