Leetcode 2241: Design an ATM Machine
Design an ATM machine that can handle deposits and withdrawals of five denominations: $20, $50, $100, $200, and $500. When withdrawing, the machine always tries to use the highest denominations available first. Implement methods to deposit money and withdraw specified amounts.
Problem
Approach
Steps
Complexity
Input: The input consists of operations performed on the ATM, including deposits and withdrawals.
Example: Input
["ATM", "deposit", "withdraw", "deposit", "withdraw", "withdraw"]
[[], [[1,2,3,0,1]], [250], [[0,1,0,1,2]], [570], [1000]]
Constraints:
• banknotesCount.length == 5
• 0 <= banknotesCount[i] <= 10^9
• 1 <= amount <= 10^9
• At most 5000 calls in total to withdraw and deposit.
• Sum of banknotesCount[i] in all deposits doesn't exceed 10^9.
Output: Output the result of each operation: null for deposits, an array of withdrawn banknotes for successful withdrawals, or [-1] if a withdrawal cannot be fulfilled.
Example: Output
[null, null, [0,0,2,0,0], null, [-1], [-1]]
Constraints:
• For successful withdrawals, the output array must be of length 5 and reflect the denominations used in the order $20, $50, $100, $200, $500.
• If a withdrawal cannot be fulfilled, output [-1].
Goal: Simulate the ATM operations while adhering to the constraints of prioritizing higher denominations for withdrawals.
Steps:
• Initialize the ATM with five denominations and their counts set to 0.
• For deposits, update the count of each denomination.
• For withdrawals, calculate the maximum possible banknotes of each denomination that can be used while satisfying the total amount.
• If the amount cannot be withdrawn exactly, return [-1] without modifying the ATM's state.
Goal: Conditions that must be followed during deposit and withdrawal operations.
Steps:
• Deposits add to the current count of banknotes in the ATM.
• Withdrawals must minimize the number of notes used by prioritizing larger denominations.
• Withdrawals are only allowed if the exact amount can be fulfilled using the available banknotes.
Assumptions:
• The ATM starts with no banknotes.
• Withdrawals are rejected if the exact amount cannot be formed.
• Deposits do not specify the order of operations; they directly add banknotes to the ATM.
• Input: Input
["ATM", "deposit", "withdraw", "deposit", "withdraw", "withdraw"]
[[], [[1,1,0,0,1]], [300], [[0,0,2,1,0]], [750], [70]]
• Explanation: 1. ATM is initialized. 2. Deposit adds $20 (1), $50 (1), and $500 (1). 3. Withdraw 300 uses $50 (1) and $500 (1). 4. Deposit adds $100 (2) and $200 (1). 5. Withdraw 750 fails as exact denominations are not available. 6. Withdraw 70 fails as $20 and $50 cannot fulfill the amount.
Approach: Use a greedy algorithm for withdrawals and maintain a dynamic count of banknotes for deposits.
Observations:
• The withdrawal process must prioritize larger denominations to minimize the number of notes used.
• Deposits are straightforward additions to the banknotes count.
• Edge cases include failed withdrawals when exact change cannot be made.
• A greedy approach works well for this problem since we prioritize larger denominations first.
Steps:
• Initialize an array to store the count of each denomination.
• For deposits, iterate through the input array and add each count to the respective denomination.
• For withdrawals, start from the highest denomination and calculate the maximum number of notes that can be used without exceeding the required amount.
• Update the ATM's state if the withdrawal is successful, or return [-1] if it fails.
Empty Inputs:
• Withdrawal amount is 0.
Large Inputs:
• Maximum banknotes or amounts near the upper limit of constraints.
Special Values:
• Withdrawal amount equals the value of one denomination.
• Withdrawal amount cannot be exactly fulfilled.
Constraints:
• Withdrawal fails if any single denomination required exceeds its count in the ATM.
vector<long long> note;
ATM() {
note.resize(5, 0);
}
void deposit(vector<int> cnt) {
for(int i = 0; i < 5; i++)
note[i] += cnt[i];
}
vector<int> withdraw(int amnt) {
int cnt500 = 0, cnt200 = 0, cnt100 = 0, cnt50 = 0, cnt20 = 0;
int taken = 0;
if(amnt >= 500) {
cnt500 = amnt / 500;
if(cnt500 > note[4]) {
cnt500 = note[4];
}
amnt -= (cnt500 * 500);
}
if(amnt >= 200) {
cnt200 = amnt / 200;
if(cnt200 > note[3]) {
cnt200 = note[3];
}
amnt -= (cnt200 * 200);
}
if(amnt >= 100) {
cnt100 = amnt / 100;
if(cnt100 > note[2]) {
cnt100 = note[2];
}
amnt -= (cnt100 * 100);
}
if(amnt >= 50) {
cnt50 = amnt / 50;
if(cnt50 > note[1]) {
cnt50 = note[1];
}
amnt -= (cnt50 * 50);
}
if(amnt >= 20) {
cnt20 = amnt / 20;
if(cnt20 > note[0]) {
cnt20 = note[0];
}
amnt -= (cnt20 * 20);
}
if(amnt != 0) return vector<int>{-1};
note[4] -= cnt500;
note[3] -= cnt200;
note[2] -= cnt100;
note[1] -= cnt50;
note[0] -= cnt20;
return vector<int>{cnt20, cnt50, cnt100, cnt200, cnt500};
}
};
/**
* Your ATM object will be instantiated and called as such:
* ATM* obj = new ATM();
* obj->deposit(banknotesCount);
* vector<int> param_2 = obj->withdraw(amount);
1 : Variable Initialization
vector<long long> note;
This line declares a vector `note` to store the count of each denomination of banknotes in the ATM.
2 : Constructor
ATM() {
Constructor for the ATM class, initializing the `note` vector with 5 elements, all set to 0, representing the initial count of banknotes.
3 : Vector Operations
note.resize(5, 0);
The `resize` function ensures that the `note` vector has 5 elements, each initialized to 0, which corresponds to the 5 types of banknotes.
4 : Deposit Method
void deposit(vector<int> cnt) {
The `deposit` function allows depositing banknotes into the ATM by taking an input vector `cnt` containing the number of banknotes of each type.
5 : Loop
for(int i = 0; i < 5; i++)
A loop iterating through the 5 types of banknotes in the ATM.
6 : Vector Operations
note[i] += cnt[i];
For each denomination, the number of banknotes deposited is added to the respective index in the `note` vector.
7 : Withdraw Method
vector<int> withdraw(int amnt) {
The `withdraw` function handles withdrawal requests by calculating how many banknotes of each denomination are needed to meet the requested amount.
8 : Variable Initialization
int cnt500 = 0, cnt200 = 0, cnt100 = 0, cnt50 = 0, cnt20 = 0;
Initialization of counters for each denomination (500, 200, 100, 50, 20) of banknotes.
9 : Variable Initialization
int taken = 0;
A variable `taken` is initialized to keep track of the total amount taken during the withdrawal process.
10 : Conditional Check
if(amnt >= 500) {
Checks if the requested amount is greater than or equal to 500, the highest denomination.
11 : Mathematical Operations
cnt500 = amnt / 500;
Calculates how many 500 denomination notes can be dispensed.
12 : Conditional Check
if(cnt500 > note[4]) {
Checks if the available number of 500 denomination notes is sufficient to fulfill the request.
13 : Variable Assignment
cnt500 = note[4];
Sets the count of 500 denomination notes to the available number in the ATM.
14 : Mathematical Operations
amnt -= (cnt500 * 500);
Deducts the withdrawn amount from the total requested amount.
15 : End of Method
return vector<int>{cnt20, cnt50, cnt100, cnt200, cnt500};
If the withdrawal is successful, the function returns the number of each denomination dispensed.
Best Case: O(1) for deposit; O(1) for withdrawal with sufficient notes.
Average Case: O(5) for both operations due to the fixed denominations.
Worst Case: O(5) for withdrawal when denominations need to be checked sequentially.
Description: Both operations are efficient as they involve a constant number of denominations.
Best Case: O(1)
Worst Case: O(1) since only a fixed array of length 5 is used.
Description: Space usage is minimal as only an array of size 5 is maintained for denominations.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus