2241. Design an ATM Machine

Problem¶

Build an ATM that tracks counts of $20, $50, $100, $200, and $500 notes. Deposits add notes; withdrawals must take as many larger notes as possible first. If that choice cannot make the exact amount, return [-1] without changing the ATM.

Example: after depositing [0, 0, 0, 3, 1], withdrawing $600 returns [-1]: the required first choice is one $500 note, even though three $200 notes could make $600.

class ATM:
    def __init__(self):
        pass

    def deposit(self, banknotesCount: list[int]) -> None:
        pass

    def withdraw(self, amount: int) -> list[int]:
        pass

Key trick¶

Calculate the entire withdrawal before changing the stored counts. For each denomination, take the smaller of the available count and the count that fits in the remaining amount.

Trap¶

Do not search for another combination when the greedy choice fails. Also, store note counts, not their monetary values, and leave the ATM unchanged on failure.

Why is it interesting?¶

It is a greedy simulation where following the specified priority matters more than finding any valid combination.

Python solution¶

class ATM:
    def __init__(self):
        self.denoms = (20, 50, 100, 200, 500)
        self.bank = [0] * 5

    def deposit(self, banknotesCount: list[int]) -> None:
        for i in range(5):
            self.bank[i] += banknotesCount[i]

    def withdraw(self, amount: int) -> list[int]:
        used = [0] * 5

        # Plan the withdrawal from largest denomination to smallest.
        for i in range(4, -1, -1):
            used[i] = min(self.bank[i], amount // self.denoms[i])
            amount -= used[i] * self.denoms[i]

        # Commit only if the planned withdrawal makes the exact amount.
        if amount:
            return [-1]

        for i in range(5):
            self.bank[i] -= used[i]
        return used

Complexity: $O(5)$ time per deposit or withdrawal and $O(5)$ space for the ATM state. A withdrawal uses another $O(5)$ temporary space.

Comment on my solution¶

deposit stores cnt * bn, but self.bank must store the number of notes: add cnt.
withdraw can take another note even when its value exceeds the remaining amount; use amount // denomination to limit the count.
The submitted code refers to self.bank_notes in withdraw, but the attribute is named self.bank_notes in __init__? In the shown code, the names match. The main failure is that one deposited $500 note is stored as 500 available notes, so the first withdrawal takes two $500 notes and rejects $600.

# Wrong Answer: 9/111 testcases passed
# Input
# ["ATM","deposit","withdraw","deposit","withdraw","withdraw"]
# [[],[[0,0,1,2,1]],[600],[[0,1,0,1,1]],[600],[550]]
# Output: [null,null,[-1],null,[-1],[-1]]
# Expected: [null,null,[0,0,1,0,1],null,[-1],[0,1,0,0,1]]
class ATM:

    def __init__(self):
        self.bank = [0] * 5 # [20,50,100,200,500]
        self.bank_notes = [20,50,100,200,500]

    def deposit(self, banknotesCount: list[int]) -> None:
        for i, cnt, bn in zip(range(5), banknotesCount, self.bank_notes):
            self.bank[i] += cnt * bn


    def withdraw(self, amount: int) -> list[int]:
        bank_notes_used = [0] * 5
        i = 4
        total = 0
        while i >= 0 and total < amount:
            if self.bank[i] == bank_notes_used[i]:
                i -= 1
                continue
            total += self.bank_notes[i]
            bank_notes_used[i] += 1
        if total == amount:
            for i in range(5):
                self.bank[i] -= bank_notes_used[i]
            return bank_notes_used
        return [-1]