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 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).
Examples
Example 1
|
|
Constraints
banknotesCount.length == 5
0 <= banknotesCount[i] <= 10^9
1 <= amount <= 10^9
- 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
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
- Maintain an array
cnt
of length 5 for the count of each denomination:[20, 50, 100, 200, 500]
. - For
deposit
, add the deposited banknotes tocnt
. - 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, updatecnt
and return the notes used. If not, return[-1]
and do not updatecnt
.
Code
|
|
|
|
|
|
|
|