LeetCode 2241 - Design an ATM Machine

The problem asks us to design a simulation of an ATM machine that can handle deposits and withdrawals with strict rules about how money is dispensed. The ATM stores five types of banknotes: 50, 200, and $500.

leetcodemediumarraygreedydesign

LeetCode Problem 2241

Difficulty: 🟡 Medium
Topics: Array, Greedy, Design

Solution

Problem Understanding

The problem asks us to design a simulation of an ATM machine that can handle deposits and withdrawals with strict rules about how money is dispensed. The ATM stores five types of banknotes: $20, $50, $100, $200, and $500. The key challenge is implementing the withdrawal logic, which prioritizes giving out larger denominations first.

The deposit function receives an array representing the count of each banknote to add to the ATM, in the order [20, 50, 100, 200, 500]. The withdraw function receives a total amount and must return an array of how many banknotes of each type will be given, or [-1] if it is impossible to satisfy the request using the priority rule. The ATM must not partially withdraw or rearrange banknotes against the largest-first policy.

Constraints indicate that the ATM can handle very large numbers of banknotes (up to 10^9 per denomination) and large withdrawal amounts (up to 10^9). With at most 5000 operations, this suggests an algorithm that loops over the five denominations is sufficient. Edge cases include trying to withdraw amounts that cannot be formed with the available notes, depositing no notes, and withdrawing the exact total in a combination of denominations.

Approaches

Brute Force Approach

A brute-force approach would attempt to generate all possible combinations of banknotes that sum to the withdrawal amount and select the one with the largest denominations first. While correct in theory, this is computationally infeasible because the number of combinations grows exponentially with the number of banknotes. Even with only five denominations, the counts can be as large as 10^9, making enumeration impossible.

Optimal Approach

The optimal approach leverages a greedy algorithm: always try to use the largest denomination first. Start from the highest denomination ($500) and take as many as possible without exceeding the withdrawal amount. Continue down to the smallest denomination. If at any point the remaining amount cannot be covered by available notes, cancel the operation and return [-1]. This works because the problem explicitly requires largest-first withdrawals; no rearrangement is allowed.

The key insight is that we do not need to check all combinations; the largest-first rule ensures a single deterministic choice at each step.

Approach Time Complexity Space Complexity Notes
Brute Force O(very large) O(very large) Enumerate all combinations of notes to meet the amount
Optimal O(1) per operation O(1) Loop through fixed 5 denominations in descending order

Algorithm Walkthrough

  1. Initialize an array banknotes of size 5 to store counts for [20, 50, 100, 200, 500].

  2. For deposit(banknotesCount), iterate through the 5 denominations and add the corresponding counts to banknotes.

  3. For withdraw(amount):

  4. Initialize a temporary array used of size 5 to track how many banknotes are used.

  5. Iterate over the denominations in descending order: $500, $200, $100, $50, $20.

  6. For each denomination, determine how many notes can be used without exceeding the remaining amount. The count is the minimum of available notes and amount // denomination.

  7. Subtract the total value of notes used from amount and record the number used in used.

  8. After all denominations, if amount is zero, commit the withdrawal by subtracting used from banknotes and return used in the original order [20,50,100,200,500].

  9. If amount is not zero, return [-1] and do not modify banknotes.

Why it works: The greedy approach works because the problem enforces a strict largest-first rule. There is no alternative combination allowed if it conflicts with the rule, so attempting smaller denominations first would violate the requirement. By iterating from largest to smallest, we correctly simulate the ATM behavior.

Python Solution

from typing import List

class ATM:
    def __init__(self):
        self.banknotes = [0] * 5  # counts for 20,50,100,200,500
        self.denominations = [20, 50, 100, 200, 500]

    def deposit(self, banknotesCount: List[int]) -> None:
        for i in range(5):
            self.banknotes[i] += banknotesCount[i]

    def withdraw(self, amount: int) -> List[int]:
        used = [0] * 5
        remaining = amount
        for i in reversed(range(5)):
            count = min(self.banknotes[i], remaining // self.denominations[i])
            used[i] = count
            remaining -= count * self.denominations[i]

        if remaining == 0:
            for i in range(5):
                self.banknotes[i] -= used[i]
            return used
        return [-1]

The __init__ method sets up the ATM with empty counts. The deposit method iterates over each denomination and adds counts. The withdraw method uses a greedy top-down loop to determine how many notes of each type can be used. If the withdrawal is feasible, the ATM's state is updated; otherwise, [-1] is returned.

Go Solution

type ATM struct {
	banknotes    [5]int
	denominations [5]int
}

func Constructor() ATM {
	return ATM{denominations: [5]int{20, 50, 100, 200, 500}}
}

func (this *ATM) Deposit(banknotesCount []int) {
	for i := 0; i < 5; i++ {
		this.banknotes[i] += banknotesCount[i]
	}
}

func (this *ATM) Withdraw(amount int) []int {
	used := [5]int{}
	remaining := amount
	for i := 4; i >= 0; i-- {
		count := remaining / this.denominations[i]
		if count > this.banknotes[i] {
			count = this.banknotes[i]
		}
		used[i] = count
		remaining -= count * this.denominations[i]
	}

	if remaining == 0 {
		for i := 0; i < 5; i++ {
			this.banknotes[i] -= used[i]
		}
		return used[:]
	}
	return []int{-1}
}

Go-specific details include using a fixed-size array for banknotes and denominations and slicing used when returning. Arithmetic operations are straightforward as integers are 64-bit by default in Go on most platforms, sufficient for constraints.

Worked Examples

Example 1

Initial deposit: [0,0,1,2,1]

Denomination Count before Withdrawal for 600 Count after
500 1 1 0
200 2 0 2
100 1 1 0
50 0 0 0
20 0 0 0

withdraw(600) → [0,0,1,0,1]

Next deposit [0,1,0,1,1] → updated counts [0,1,0,3,1]

Attempt withdraw(600) → machine tries 500 first → 1 note used, remaining 100 → only 50 and 20 available to fill 100 → cannot satisfy → returns [-1].

withdraw(550) → 500 first → 1 note, remaining 50 → 50 note used → returns [0,1,0,0,1]

Complexity Analysis

Measure Complexity Explanation
Time O(1) per operation Only loops over 5 denominations
Space O(1) Stores 5 integers for banknotes and 5 for denominations

Even with 5000 operations, the total time is negligible.

Test Cases

atm = ATM()
atm.deposit([0,0,1,2,1])
assert atm.withdraw(600) == [0,0,1,0,1]  # Uses 1x500 + 1x100
atm.deposit([0,1,0,1,1])
assert atm.withdraw(600) == [-1]         # Cannot complete with largest-first rule
assert atm.withdraw(550) == [0,1,0,0,1]  # Uses 1x500 + 1x50
atm.deposit([0,0,0,0,0])
assert atm.withdraw(20) == [-1]          # Nothing to withdraw
atm.deposit([1,0,0,0,0])
assert atm.withdraw(20) == [1,0,0,0,0]   # Withdraw exactly one $20
atm.deposit([10**9, 10**9, 10**9, 10**9, 10**9])
assert atm.withdraw(10**9*500) == [0,0,0,0,10**9]  # Large scale
Test Why
[0,0,1,2,1] withdraw