{x}
blog image

Design an ATM Machine

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 are 2 $50 banknotes, 1 $100 banknote, and 1 $200 banknote, then the machine will use the $100 and $200 banknotes.
  • However, if you try to withdraw $600 and there are 3 $200 banknotes and 1 $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 length 5 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).

 

Example 1:

Input
["ATM", "deposit", "withdraw", "deposit", "withdraw", "withdraw"]
[[], [[0,0,1,2,1]], [600], [[0,1,0,1,1]], [600], [550]]
Output
[null, null, [0,0,1,0,1], null, [-1], [0,1,0,0,1]]

Explanation
ATM atm = new ATM();
atm.deposit([0,0,1,2,1]); // Deposits 1 $100 banknote, 2 $200 banknotes,
                          // and 1 $500 banknote.
atm.withdraw(600);        // Returns [0,0,1,0,1]. The machine uses 1 $100 banknote
                          // and 1 $500 banknote. The banknotes left over in the
                          // machine are [0,0,0,2,0].
atm.deposit([0,1,0,1,1]); // Deposits 1 $50, $200, and $500 banknote.
                          // The banknotes in the machine are now [0,1,0,3,1].
atm.withdraw(600);        // Returns [-1]. The machine will try to use a $500 banknote
                          // and then be unable to complete the remaining $100,
                          // so the withdraw request will be rejected.
                          // Since the request is rejected, the number of banknotes
                          // in the machine is not modified.
atm.withdraw(550);        // Returns [0,1,0,0,1]. The machine uses 1 $50 banknote
                          // and 1 $500 banknote.

 

Constraints:

  • banknotesCount.length == 5
  • 0 <= banknotesCount[i] <= 109
  • 1 <= amount <= 109
  • At most 5000 calls in total will be made to withdraw and deposit.
  • At least one call will be made to each function withdraw and deposit.
  • Sum of banknotesCount[i] in all deposits doesn't exceed 109

Solution Explanation: Design an ATM Machine

This problem requires designing an ATM class that handles deposits and withdrawals of banknotes of five different denominations: $20, $50, $100, $200, and $500. The ATM prioritizes using larger denominations when withdrawing.

Approach

The solution uses a straightforward simulation approach. We maintain an internal array (cnt in the code examples) to track the count of each denomination of banknotes currently in the ATM.

Deposit: The deposit operation simply adds the deposited banknotes to the corresponding counts in the cnt array. This is a constant time operation, O(1).

Withdraw: The withdraw operation is slightly more complex:

  1. Iteration: It iterates through the denominations from largest to smallest ($500 to $20).
  2. Greedy Approach: For each denomination, it calculates how many banknotes of that denomination can be used without exceeding the requested amount. It uses min(amount / denomination, current_count) to determine this, ensuring we don't use more banknotes than are available.
  3. Update Amount: The amount is updated by subtracting the value of the withdrawn banknotes.
  4. Check for Success: If after iterating through all denominations, the amount is still greater than 0, it means the withdrawal request cannot be fulfilled, and [-1] is returned.
  5. Update Counts: If the withdrawal is successful, the cnt array is updated to reflect the reduced number of banknotes.
  6. Return Result: The array representing the number of banknotes of each denomination used in the withdrawal is returned.

The time complexity of the withdraw operation is also O(1) because the number of denominations is fixed (5). The space complexity is O(1) as well because we use a fixed-size array to store the banknote counts.

Code in Different Languages

The code implementations in Python, Java, C++, Go, and TypeScript all follow the same logic described above. They differ only in syntax and specific language features. Each example includes comments to help understand the code's functionality.

Time and Space Complexity Analysis

  • Time Complexity:

    • deposit: O(1) - Constant time operation.
    • withdraw: O(1) - Constant time operation (fixed number of denominations).

  • Space Complexity: O(1) - Constant space used to store the banknote counts (fixed-size array). The space used does not scale with the input size.

The overall solution is efficient for the given constraints, as the number of operations (deposits and withdrawals) and the number of denominations are relatively small.