2241. Design an ATM Machine
Description
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 are2
$50
banknotes,1
$100
banknote, and1
$200
banknote, then the machine will use the$100
and$200
banknotes. - However, if you try to withdraw
$600
and there are3
$200
banknotes and1
$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 length5
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 towithdraw
anddeposit
. - At least one call will be made to each function
withdraw
anddeposit
. - Sum of
banknotesCount[i]
in all deposits doesn't exceed109
Solutions
Solution 1: Simulation
We use an array $d$ to record the denominations of the bills and an array $cnt$ to record the number of bills for each denomination.
For the deposit
operation, we only need to add the number of bills for the corresponding denomination. The time complexity is $O(1)$.
For the withdraw
operation, we enumerate the bills from largest to smallest denomination, taking out as many bills as possible without exceeding the $amount$. Then, we subtract the total value of the withdrawn bills from $amount$. If $amount$ is still greater than $0$ at the end, it means it's not possible to withdraw the $amount$ with the available bills, and we return $-1$. Otherwise, we return the number of bills withdrawn. The time complexity is $O(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 |
|
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 34 35 |
|
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 34 35 36 37 |
|