Problem

There is an ATM machine that stores banknotes of 5 denominations: 20, 50, 100, 200, and 500 dollars. Initially the ATM is empty. The user can use the machine to deposit or withdraw any amount of money.

When withdrawing, the machine prioritizes using banknotes of larger values.

  • For example, if you want to withdraw $300 and there are 2 $50 banknotes, 1 $100 banknote, and 1 $200 banknote, then the machine will use the $100 and $200 banknotes.
  • However, if you try to withdraw $600 and there are 3 $200 banknotes and 1 $500 banknote, then the withdraw request will be rejected because the machine will first try to use the $500 banknote and then be unable to use banknotes to complete the remaining $100. Note that the machine is not allowed to use the $200 banknotes instead of the $500 banknote.

Implement the ATM class:

  • ATM() Initializes the ATM object.
  • void deposit(int[] banknotesCount) Deposits new banknotes in the order $20, $50, $100, $200, and $500.
  • int[] withdraw(int amount) Returns an array of length 5 of the number of banknotes that will be handed to the user in the order $20, $50, $100, $200, and $500, and update the number of banknotes in the ATM after withdrawing. Returns [-1] if it is not possible (do not withdraw any banknotes in this case).

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

**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**
ATM atm = new ATM();
atm.deposit([0,0,1,2,1]); // Deposits 1 $100 banknote, 2 $200 banknotes,
                          // and 1 $500 banknote.
atm.withdraw(600);        // Returns [0,0,1,0,1]. The machine uses 1 $100 banknote
                          // and 1 $500 banknote. The banknotes left over in the
                          // machine are [0,0,0,2,0].
atm.deposit([0,1,0,1,1]); // Deposits 1 $50, $200, and $500 banknote.
                          // The banknotes in the machine are now [0,1,0,3,1].
atm.withdraw(600);        // Returns [-1]. The machine will try to use a $500 banknote
                          // and then be unable to complete the remaining $100,
                          // so the withdraw request will be rejected.
                          // Since the request is rejected, the number of banknotes
                          // in the machine is not modified.
atm.withdraw(550);        // Returns [0,1,0,0,1]. The machine uses 1 $50 banknote
                          // and 1 $500 banknote.

Constraints

  • banknotesCount.length == 5
  • 0 <= banknotesCount[i] <= 10^9
  • 1 <= amount <= 10^9
  • At most 5000 calls in total will be made to withdraw and deposit.
  • At least one call will be made to each function withdraw and deposit.
  • Sum of banknotesCount[i] in all deposits doesn’t exceed 109

Solution

Method 1 – Greedy Simulation with Largest Denomination First

Intuition

To simulate the ATM, always use the largest available banknotes first when withdrawing. For deposits, simply add the counts to the respective denominations. For withdrawals, try to use as many of the largest denomination as possible, then move to the next smaller one, and so on. If the amount cannot be formed exactly, the withdrawal fails and the ATM state is unchanged.

Approach

  1. Maintain an array cnt of length 5 for the count of each denomination: [20, 50, 100, 200, 500].
  2. For deposit, add the deposited banknotes to cnt.
  3. For withdraw, starting from the largest denomination, use as many as possible without exceeding the amount or available notes. Track the notes used in a temporary array. If the amount becomes zero, update cnt and return the notes used. If not, return [-1] and do not update cnt.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class ATM:
    def __init__(self):
        self.notes = [20, 50, 100, 200, 500]
        self.cnt = [0] * 5
    def deposit(self, banknotesCount: list[int]) -> None:
        for i in range(5):
            self.cnt[i] += banknotesCount[i]
    def withdraw(self, amount: int) -> list[int]:
        use = [0] * 5
        for i in range(4, -1, -1):
            take = min(self.cnt[i], amount // self.notes[i])
            use[i] = take
            amount -= take * self.notes[i]
        if amount == 0:
            for i in range(5):
                self.cnt[i] -= use[i]
            return use
        return [-1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public class ATM {
    private final int[] notes = {20, 50, 100, 200, 500};
    private final long[] cnt = new long[5];
    public ATM() {}
    public void deposit(int[] banknotesCount) {
        for (int i = 0; i < 5; i++) cnt[i] += banknotesCount[i];
    }
    public int[] withdraw(int amount) {
        int[] use = new int[5];
        for (int i = 4; i >= 0; i--) {
            int take = (int)Math.min(cnt[i], amount / notes[i]);
            use[i] = take;
            amount -= take * notes[i];
        }
        if (amount == 0) {
            for (int i = 0; i < 5; i++) cnt[i] -= use[i];
            return use;
        }
        return new int[]{-1};
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class ATM {
    vector<long long> cnt;
    vector<int> notes = {20, 50, 100, 200, 500};
public:
    ATM() : cnt(5) {}
    void deposit(vector<int> banknotesCount) {
        for (int i = 0; i < 5; ++i) cnt[i] += banknotesCount[i];
    }
    vector<int> withdraw(int amount) {
        vector<int> use(5);
        for (int i = 4; i >= 0; --i) {
            int take = min((long long)cnt[i], amount / notes[i]);
            use[i] = take;
            amount -= take * notes[i];
        }
        if (amount == 0) {
            for (int i = 0; i < 5; ++i) cnt[i] -= use[i];
            return use;
        }
        return {-1};
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

type ATM struct {
    notes [5]int
    cnt   [5]int64
}
func Constructor() ATM {
    return ATM{notes: [5]int{20, 50, 100, 200, 500}}
}
func (a *ATM) Deposit(banknotesCount []int) {
    for i := 0; i < 5; i++ {
        a.cnt[i] += int64(banknotesCount[i])
    }
}
func (a *ATM) Withdraw(amount int) []int {
    use := make([]int, 5)
    for i := 4; i >= 0; i-- {
        take := int(min(a.cnt[i], int64(amount/a.notes[i])))
        use[i] = take
        amount -= take * a.notes[i]
    }
    if amount == 0 {
        for i := 0; i < 5; i++ {
            a.cnt[i] -= int64(use[i])
        }
        return use
    }
    return []int{-1}
}
func min(a, b int64) int64 {
    if a < b {
        return a
    }
    return b
}