Design an ATM Machine — LeetCode 2241 Python Solution
MediumGreedyDesignArray
- Problem
- #2241
- Pattern
- Greedy
- 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
Python
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
| Measure | Complexity |
|---|---|
| Time | O(1) |
| Space | O(1) to O(n) auxiliary |
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
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.