Problem statement

An ATM holds banknotes of five values: 20, 50, 100, 200 and 500 dollars, and starts empty.

To pay out an amount, the machine always uses the largest notes first: it takes as many 500s as it can without going over the amount, then as many 200s as it can for what is left, and so on down to the 20s. If that greedy pass does not reach the amount exactly, the withdrawal is refused and no notes leave the machine — even if some other choice of notes would have worked.

For example, with three $200 notes and one $500 note, a request for $600 takes the $500, then cannot make the remaining $100 out of $200s, so it is refused.

Write the class ATM:

• ATM() creates an empty machine.
• void deposit(int[] banknotesCount) adds banknotesCount[i] notes of the i-th value, in the order [20, 50, 100, 200, 500].
• int[] withdraw(int amount) returns how many notes of each value (same order) were paid out, or [-1] if the withdrawal is refused.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["ATM","deposit","withdraw","deposit","withdraw","withdraw"]
[[],[[0,0,1,2,1]],[600],[[0,1,0,1,1]],[600],[550]]
Output: [null,null,[0,0,1,0,1],null,[-1],[0,1,0,0,1]]
Explanation: The first $600 is one $500 and one $100. After the second deposit the machine holds 1×50, 3×200 and 1×500: $600 takes the $500, then no $200 fits into $100 and the $50 leaves $50 that no note covers, so it is refused. $550 is the $500 plus the $50.

Example 2

Input: ["ATM","withdraw","deposit","withdraw","withdraw","deposit","withdraw"]
[[],[40],[[5,0,0,0,0]],[60],[70],[[0,1,0,0,0]],[70]]
Output: [null,[-1],null,[3,0,0,0,0],[-1],null,[1,1,0,0,0]]
Explanation: An empty machine refuses $40. $60 is three $20s, leaving two. $70 needs a $50 the machine does not have yet; after one is deposited it pays 1×20 + 1×50.

Constraints

• banknotesCount.length == 5
• 0 <= banknotesCount[i] <= 10^9
• 1 <= amount <= 10^9
• At most 5000 calls are made in total to deposit and withdraw
• At least one call is made to each of deposit and withdraw
• The machine may hold more than 2^31 - 1 notes of one value, so store the counts in 64-bit integers; every answer fits in 32 bits

Hints for Design an ATM Machine

1. Hint 1

   The order of note values is fixed and the rule is fixed: largest first. Simulate it exactly — do not search for a better combination.

2. Hint 2

   For each value from $500 down to $20 take min(available, remaining / value) notes.

3. Hint 3

   Work on a copy of the counts (or just record what you would take) and only subtract from the machine once you know the remainder reached 0.

How to solve Design an ATM Machine

The withdrawal rule is a greedy pass that the problem prescribes, so there is nothing to optimise: walk the five values from largest to smallest, take as many of each as fit, and commit the result only if the remainder is exactly zero.

Approach

1. Keep count[0..4] (64-bit) for the values [20, 50, 100, 200, 500].
2. deposit: add each banknotesCount[i] to count[i].
3. withdraw(amount): for i = 4 down to 0, let take[i] = min(count[i], amount / value[i]) and subtract take[i] * value[i] from amount.
4. If amount is not 0 afterwards, return [-1] and leave the counts alone.
5. Otherwise subtract take from count and return take.

Why it works

Taking min(count, remaining / value) notes is exactly "as many as possible without exceeding the remaining amount", which is the machine's rule at every value. Because the counts are only changed after the pass succeeds, a refused withdrawal leaves the machine untouched.

Complexity

• Time — O(1) per call (five note values)
• Space — O(1)

Pitfalls

• Deposits of up to 10^9 notes, 5000 times, overflow a 32-bit count — use 64-bit integers for the stored counts.
• Do not subtract while scanning: a refused withdrawal must not change the machine.
• A smarter combination does not count: with 3×$200 and 1×$500, $600 is refused even though 3×$200 would pay it.

Reference solution

Python

class ATM:

    def __init__(self):
        self.notes = [20, 50, 100, 200, 500]
        self.count = [0] * 5

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

    def withdraw(self, amount: int) -> List[int]:
        take = [0] * 5
        for i in range(4, -1, -1):  # largest notes first
            take[i] = min(self.count[i], amount // self.notes[i])
            amount -= take[i] * self.notes[i]
        if amount != 0:
            return [-1]  # refused: the machine keeps every note
        for i in range(5):
            self.count[i] -= take[i]
        return take

Java

class ATM {
    private static final int[] NOTES = {20, 50, 100, 200, 500};
    private long[] count = new long[5];

    public ATM() {
    }

    public void deposit(int[] banknotesCount) {
        for (int i = 0; i < 5; i++) count[i] += banknotesCount[i];
    }

    public int[] withdraw(int amount) {
        int[] take = new int[5];
        for (int i = 4; i >= 0; i--) { // largest notes first
            take[i] = (int) Math.min(count[i], amount / NOTES[i]);
            amount -= take[i] * NOTES[i];
        }
        if (amount != 0) return new int[]{-1}; // refused: the machine keeps every note
        for (int i = 0; i < 5; i++) count[i] -= take[i];
        return take;
    }
}

C++

class ATM {
    const int notes[5] = {20, 50, 100, 200, 500};
    long long count[5] = {0, 0, 0, 0, 0};
public:
    ATM() {}

    void deposit(vector<int>& banknotesCount) {
        for (int i = 0; i < 5; i++) count[i] += banknotesCount[i];
    }

    vector<int> withdraw(int amount) {
        vector<int> take(5, 0);
        for (int i = 4; i >= 0; i--) { // largest notes first
            take[i] = (int)min(count[i], (long long)(amount / notes[i]));
            amount -= take[i] * notes[i];
        }
        if (amount != 0) return {-1}; // refused: the machine keeps every note
        for (int i = 0; i < 5; i++) count[i] -= take[i];
        return take;
    }
};

JavaScript

var ATM = function() {
    this.notes = [20, 50, 100, 200, 500];
    this.count = [0, 0, 0, 0, 0]; // doubles: exact far beyond 5000 * 10^9
};

ATM.prototype.deposit = function(banknotesCount) {
    for (var i = 0; i < 5; i++) this.count[i] += banknotesCount[i];
};

ATM.prototype.withdraw = function(amount) {
    var take = [0, 0, 0, 0, 0];
    for (var i = 4; i >= 0; i--) { // largest notes first
        take[i] = Math.min(this.count[i], Math.floor(amount / this.notes[i]));
        amount -= take[i] * this.notes[i];
    }
    if (amount !== 0) return [-1]; // refused: the machine keeps every note
    for (var j = 0; j < 5; j++) this.count[j] -= take[j];
    return take;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design Bitset Medium
• Range Frequency Queries Medium
• Simple Bank System Medium