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.
$300 and there are 2 $50 banknotes, 1 $100 banknote, and 1 $200 banknote, then the machine will use the $100 and $200 banknotes.$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 == 50 <= banknotesCount[i] <= 1091 <= amount <= 1095000 calls in total will be made to withdraw and deposit.withdraw and deposit.banknotesCount[i] in all deposits doesn't exceed 109This approach uses a greedy algorithm that starts by attempting to fulfill the withdrawal request using the largest denominations available. The solution maintains an array to hold the count of each denomination in the ATM. During withdrawal, it tries to use the largest denominations first and updates the array accordingly.
This C solution makes use of a structure for ATM which maintains the banknotes array representing the count of each denomination. The 'deposit' function adds the respective counts to the banknotes array, while the 'withdraw' function tries to fulfill a withdrawal request starting from the largest denomination, updating the array appropriately. If a withdrawal cannot be fulfilled, it returns an array with -1.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1) for both deposit and withdraw since we are iterating over a constant number of denominations.
Space Complexity: O(1) since we are only storing the state of banknotes in the ATM.
In this approach, we can use a dictionary (or hash map) structure instead of arrays to store and access the banknotes. This allows for more flexibility if additional denominations are introduced in the future.
This is a Python solution using dictionary to store the counts of banknotes, which can easily handle changes in denominations. The deposit method adds numbers to corresponding denominations, and the withdraw method starts using the highest denominations while adjusting the withdrawal amount. If it can fully meet the withdrawal, it deducts used notes and returns the count of each denomination, otherwise returns [-1] if it's not possible.
JavaScript
Time Complexity: O(1) for both operations since they work over a constant set of keys.
Space Complexity: O(1) due to the fixed storage needs.
| Approach | Complexity |
|---|---|
| Greedy Approach Using Arrays | Time Complexity: O(1) for both deposit and withdraw since we are iterating over a constant number of denominations. |
| Hash Map Approach | Time Complexity: O(1) for both operations since they work over a constant set of keys. |
Coin Change - Dynamic Programming Bottom Up - Leetcode 322 • NeetCode • 574,201 views views
Watch 9 more video solutions →Practice Design an ATM Machine with our built-in code editor and test cases.
Practice on FleetCode