MediumNo. 2241
Design an ATM Machine — LeetCode 2241 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, Design, Array
- Reading time
- 5 min
- Source
- leetcode.com
The problem
There is an ATM machine that stores banknotes of 5 denominations: 20, 50, 100, 200, and 500 dollars. Initially the ATM is empty.
Example
- Input
- ["ATM", "deposit", "withdraw", "deposit", "withdraw", "withdraw"]
- Output
- [null, null, [0,0,1,0,1], null, [-1], [0,1,0,0,1]]
- Explanation
- ATM atm = new ATM();
Python solution
class ATM:
def __init__(self):
self.d = [20, 50, 100, 200, 500]
self.m = len(self.d)
self.cnt = [0] * self.m
def deposit(self, banknotesCount: List[int]) -> None:
for i, x in enumerate(banknotesCount):
self.cnt[i] += x
def withdraw(self, amount: int) -> List[int]:
ans = [0] * self.m
for i in reversed(range(self.m)):
ans[i] = min(amount // self.d[i], self.cnt[i])
amount -= ans[i] * self.d[i]
if amount > 0:
return [-1]
for i, x in enumerate(ans):
self.cnt[i] -= x
return ans
# Your ATM object will be instantiated and called as such:
# obj = ATM()
# obj.deposit(banknotesCount)
# param_2 = obj.withdraw(amount)Complexity
- Time
- O(1)
- Space · auxiliary
- O(1) to O(n)
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 2241. Design an ATM Machine is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2234 | Maximum Total Beauty of the Gardens | Hard |
| 2233 | Maximum Product After K Increments | Medium |
| 0011 | Container With Most Water | Medium |
| 0134 | Gas Station | Medium |
| 0135 | Candy | Hard |
| 0179 | Largest Number | Medium |
Frequently asked questions
- How hard is LeetCode 2241. Design an ATM Machine?
LeetCode 2241. Design an ATM Machine is rated Medium on LeetCode.
- What topics does LeetCode 2241. Design an ATM Machine cover?
LeetCode 2241. Design an ATM Machine is tagged Greedy, Design and Array on LeetCode.