# Design an ATM Machine
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/design-an-atm-machine)
Canonical: https://scaleengineer.com/dsa/problems/design-an-atm-machine
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Array
**Companies:** [Yandex](https://scaleengineer.com/companies/yandex)
---
## 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).

**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**
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] <= 109`
* `1 <= amount <= 109`
* 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`

# Approaches
## Simulation using TreeMap
This approach simulates the ATM operations using a `TreeMap` to store the banknote counts. The keys of the map are the banknote denominations (e.g., 500, 200), and the values are their respective counts. A `TreeMap` with a reverse order comparator is used to automatically keep the denominations sorted from largest to smallest, which simplifies the withdrawal logic by allowing direct iteration in the prioritized order.
**Time:** O(1) - For each operation, the complexity is technically O(k log k) where k is the number of denominations. Since k is a small constant (5), the overall time complexity is constant, O(1). However, the constant factor is larger than in the array-based approach due to map operations. · **Space:** O(1) - The space used is constant because the number of denominations (k=5) is fixed. We store a map and an array of size k.
**Pros:** The code can be more descriptive as it uses actual denomination values as keys instead of array indices.; This approach is flexible. If the set of denominations were to change, a `TreeMap` could handle it more dynamically than a fixed-size array (though this is not a requirement of the current problem).
**Cons:** Slightly more complex to implement compared to a simple array-based solution.; Less performant due to the overhead of `TreeMap` operations (logarithmic time complexity for gets and puts) and object creation for map entries.; Requires an extra mapping step to convert between the problem's array index format and the map's key-based format for input and output.
### Explanation
The core idea is to use a data structure that naturally handles sorted keys to represent the denominations. A `TreeMap` is a good fit for this. We store the count of each banknote denomination as a `long` to prevent overflow, as the number of notes can be large.

**Initialization (`ATM()`):**
We initialize a `TreeMap<Integer, Long>` with a reverse order comparator. This ensures that when we iterate over its keys or entries, they are processed in descending order (500, 200, 100, 50, 20), which is exactly what the withdrawal logic requires.

**Deposit (`deposit(int[] banknotesCount)`):**
For a deposit, we iterate through the input `banknotesCount` array. For each index `i`, we find the corresponding denomination value and update its count in the `TreeMap`.

**Withdraw (`withdraw(int amount)`):**
For a withdrawal, we follow the specified greedy algorithm. We iterate through the `TreeMap`'s entries (from largest to smallest denomination). For each denomination, we calculate the maximum number of banknotes we can take without exceeding the remaining amount or the available count. We keep track of the notes to be withdrawn. If we can satisfy the entire amount, we finalize the transaction by updating the counts in the `TreeMap` and returning the result. If any amount is left over after checking all denominations, the transaction is impossible, and we return `[-1]`.

```java
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

class ATM {
    private TreeMap<Integer, Long> bank;
    private int[] denominations = {20, 50, 100, 200, 500};
    private Map<Integer, Integer> denToIndex;

    public ATM() {
        bank = new TreeMap<>(Collections.reverseOrder());
        denToIndex = new HashMap<>();
        for (int i = 0; i < 5; i++) {
            bank.put(denominations[i], 0L);
            denToIndex.put(denominations[i], i);
        }
    }

    public void deposit(int[] banknotesCount) {
        for (int i = 0; i < 5; i++) {
            int den = denominations[i];
            bank.put(den, bank.get(den) + banknotesCount[i]);
        }
    }

    public int[] withdraw(int amount) {
        long currentAmount = amount;
        int[] result = new int[5];

        for (Map.Entry<Integer, Long> entry : bank.entrySet()) {
            int den = entry.getKey();
            long count = entry.getValue();

            long numNotes = Math.min(currentAmount / den, count);
            
            result[denToIndex.get(den)] = (int) numNotes;
            currentAmount -= numNotes * den;
        }

        if (currentAmount > 0) {
            return new int[]{-1};
        }

        // Update bank counts after a successful withdrawal
        for (int i = 0; i < 5; i++) {
            int den = denominations[i];
            bank.put(den, bank.get(den) - result[i]);
        }
        
        return result;
    }
}
```
### Algorithm
- In the `ATM` class, initialize a `denominations` array `{20, 50, 100, 200, 500}`.
- Use a `TreeMap<Integer, Long>` with a reverse order comparator to store banknote counts, mapping denomination values to their counts. Initialize all counts to 0.
- **`deposit(int[] banknotesCount)`**:
  - Iterate through the input `banknotesCount` array from `i = 0` to `4`.
  - For each index `i`, get the corresponding denomination `d = denominations[i]`.
  - Update the count in the `TreeMap`: `map.put(d, map.get(d) + banknotesCount[i])`.
- **`withdraw(int amount)`**:
  - Create a temporary map or array to store the number of notes to be withdrawn for each denomination.
  - Iterate through the `TreeMap`'s entries. Since we used a reverse order comparator, this will be from the largest denomination to the smallest.
  - For each denomination `d` with available count `c`, calculate the number of notes to take: `notesToTake = min(amount / d, c)`.
  - Record `notesToTake` and update the remaining `amount` by subtracting `notesToTake * d`.
  - After iterating through all denominations, check if the remaining `amount` is zero.
  - If `amount` is 0, the withdrawal is successful. Update the main `TreeMap` with the new counts and return an array representing the withdrawn notes.
  - If `amount` is not 0, the withdrawal is impossible. Return `[-1]` without modifying the ATM's state.

## Simulation using Arrays
This approach uses two simple arrays to manage the ATM's state: a `long` array for the counts of each banknote and an `int` array for the corresponding denomination values. The indices of the arrays are implicitly linked. This method is highly efficient because it relies on direct array indexing, which is a constant time operation.
**Time:** O(1) - All operations (`deposit` and `withdraw`) involve a loop that runs a fixed number of times (5), making their time complexity constant. · **Space:** O(1) - The space complexity is constant as we only use two fixed-size arrays (size 5) regardless of the number of operations.
**Pros:** Highly efficient due to the use of arrays and direct indexing, resulting in O(1) time complexity for all operations.; Simple, clean, and easy to implement and understand.; Minimal memory overhead.; The array-based structure naturally aligns with the input and output format specified in the problem.
**Cons:** The code is slightly less descriptive as it relies on indices (0-4) to represent denominations.; It's less flexible if the set of denominations were dynamic, as it's hardcoded for 5 specific denominations.
### Explanation
This is the most straightforward and performant way to solve the problem. We use a `long` array of size 5, `counts`, where `counts[i]` stores the number of banknotes of the i-th denomination. A separate `int` array, `denominations`, stores the value of each banknote, so `denominations[0]` is 20, `denominations[1]` is 50, and so on.

**Initialization (`ATM()`):**
The constructor initializes the `counts` array to all zeros and sets up the `denominations` array.

**Deposit (`deposit(int[] banknotesCount)`):**
Depositing is a simple loop that adds the values from the input `banknotesCount` array to our `counts` array.

**Withdraw (`withdraw(int amount)`):**
The withdrawal logic directly implements the required greedy strategy. It iterates backward through the arrays (from index 4 to 0) to process denominations from largest to smallest. In each step, it calculates how many notes of the current denomination can be used. If the total amount can be formed this way, the `counts` array is updated, and the result is returned. Otherwise, no changes are made, and `[-1]` is returned.

```java
class ATM {
    private long[] counts;
    private int[] denominations;

    public ATM() {
        counts = new long[5];
        denominations = new int[]{20, 50, 100, 200, 500};
    }
    
    public void deposit(int[] banknotesCount) {
        for (int i = 0; i < 5; i++) {
            counts[i] += banknotesCount[i];
        }
    }
    
    public int[] withdraw(int amount) {
        long remainingAmount = amount;
        int[] result = new int[5];
        
        for (int i = 4; i >= 0; i--) {
            int den = denominations[i];
            long availableNotes = counts[i];
            
            // Calculate how many notes of the current denomination to take
            long notesToTake = Math.min(remainingAmount / den, availableNotes);
            
            result[i] = (int)notesToTake;
            remainingAmount -= notesToTake * den;
        }
        
        // If we couldn't make the exact amount, the withdrawal is invalid
        if (remainingAmount > 0) {
            return new int[]{-1};
        }
        
        // If successful, update the ATM's banknote counts
        for (int i = 0; i < 5; i++) {
            counts[i] -= result[i];
        }
        
        return result;
    }
}
```
### Algorithm
- In the `ATM` class, initialize a `long[] counts` of size 5 to all zeros to store banknote counts.
- Also, initialize a final `int[] denominations = {20, 50, 100, 200, 500}` to map array indices to banknote values.
- **`deposit(int[] banknotesCount)`**:
  - Iterate from `i = 0` to `4`.
  - Add the deposited count to the existing count: `counts[i] += banknotesCount[i]`.
- **`withdraw(int amount)`**:
  - Create a result array `int[] result = new int[5]`.
  - Use a `long` variable `remainingAmount` initialized with `amount`.
  - Iterate backwards from `i = 4` down to `0` (from $500 to $20).
  - For each index `i`, calculate the number of notes to take: `notesToTake = min(remainingAmount / denominations[i], counts[i])`.
  - Store this number in `result[i]`.
  - Decrease `remainingAmount` by `notesToTake * denominations[i]`.
  - After the loop, if `remainingAmount` is 0, the withdrawal is successful.
    - Update the `counts` array by subtracting the `result` array's values.
    - Return `result`.
  - If `remainingAmount` is greater than 0, the withdrawal is not possible. Return `[-1]`.

# Solutions
### Java

```java
class ATM { private long [] cnt = new long [ 5 ]; private int [] d = { 20 , 50 , 100 , 200 , 500 }; public ATM () { } public void deposit ( int [] banknotesCount ) { for ( int i = 0 ; i < banknotesCount . length ; ++ i ) { cnt [ i ] += banknotesCount [ i ]; } } public int [] withdraw ( int amount ) { int [] ans = new int [ 5 ]; for ( int i = 4 ; i >= 0 ; -- i ) { ans [ i ] = ( int ) Math . min ( amount / d [ i ], cnt [ i ]); amount -= ans [ i ] * d [ i ]; } if ( amount > 0 ) { return new int [] {- 1 }; } for ( int i = 0 ; i < 5 ; ++ i ) { cnt [ i ] -= ans [ i ]; } return ans ; } } /** * Your ATM object will be instantiated and called as such: * ATM obj = new ATM(); * obj.deposit(banknotesCount); * int[] param_2 = obj.withdraw(amount); */
```

### CPP

```cpp
class ATM { public: ATM () { } void deposit ( vector < int > banknotesCount ) { for ( int i = 0 ; i < banknotesCount . size (); ++ i ) { cnt [ i ] += banknotesCount [ i ]; } } vector < int > withdraw ( int amount ) { vector < int > ans ( 5 ); for ( int i = 4 ; ~ i ; -- i ) { ans [ i ] = min ( 1ll * amount / d [ i ], cnt [ i ]); amount -= ans [ i ] * d [ i ]; } if ( amount > 0 ) { return { - 1 }; } for ( int i = 0 ; i < 5 ; ++ i ) { cnt [ i ] -= ans [ i ]; } return ans ; } private: long long cnt [ 5 ] = { 0 }; int d [ 5 ] = { 20 , 50 , 100 , 200 , 500 }; }; /** * Your ATM object will be instantiated and called as such: * ATM* obj = new ATM(); * obj->deposit(banknotesCount); * vector<int> param_2 = obj->withdraw(amount); */
```

### Python

```python
class ATM : def __init__ ( self ): self . cnt = [ 0 ] * 5 self . d = [ 20 , 50 , 100 , 200 , 500 ] def deposit ( self , banknotesCount : List [ int ]) -> None : for i , v in enumerate ( banknotesCount ): self . cnt [ i ] += v def withdraw ( self , amount : int ) -> List [ int ]: ans = [ 0 ] * 5 for i in range ( 4 , - 1 , - 1 ): ans [ i ] = min ( amount // self . d [ i ], self . cnt [ i ]) amount -= ans [ i ] * self . d [ i ] if amount > 0 : return [ - 1 ] for i , v in enumerate ( ans ): self . cnt [ i ] -= v return ans # Your ATM object will be instantiated and called as such: # obj = ATM() # obj.deposit(banknotesCount) # param_2 = obj.withdraw(amount)
```