Skip to content

Latest commit

 

History

History
299 lines (240 loc) · 9.34 KB

README_EN.md

File metadata and controls

299 lines (240 loc) · 9.34 KB
comments difficulty edit_url rating source tags
true
Medium
1616
Biweekly Contest 76 Q3
Greedy
Design
Array

2241. Design an ATM Machine

中文文档

Description

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

Solutions

Solution 1: Simulation

We use an array $\textit{d}$ to record the denominations of the bills and an array $\textit{cnt}$ to record the number of bills for each denomination.

For the deposit operation, we simply add the number of bills to the corresponding denomination. The time complexity is $O(1)$.

For the withdraw operation, we enumerate the bills from largest to smallest denomination, taking out as many bills as possible without exceeding $\textit{amount}$. We then subtract the total value of the withdrawn bills from $\textit{amount}$. If $\textit{amount}$ is still greater than $0$ at the end, it means we cannot withdraw the requested amount, and we return $-1$. Otherwise, we return the number of withdrawn bills. The time complexity is $O(1)$.

Python3

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)

Java

class ATM {
    private int[] d = {20, 50, 100, 200, 500};
    private int m = d.length;
    private long[] cnt = new long[5];

    public ATM() {
    }

    public void deposit(int[] banknotesCount) {
        for (int i = 0; i < banknotesCount.length; ++i) {
            cnt[i] += banknotesCount[i];
        }
    }

    public int[] withdraw(int amount) {
        int[] ans = new int[m];
        for (int i = m - 1; i >= 0; --i) {
            ans[i] = (int) Math.min(amount / d[i], cnt[i]);
            amount -= ans[i] * d[i];
        }
        if (amount > 0) {
            return new int[] {-1};
        }
        for (int i = 0; i < m; ++i) {
            cnt[i] -= ans[i];
        }
        return ans;
    }
}

/**
 * Your ATM object will be instantiated and called as such:
 * ATM obj = new ATM();
 * obj.deposit(banknotesCount);
 * int[] param_2 = obj.withdraw(amount);
 */

C++

class ATM {
public:
    ATM() {
    }

    void deposit(vector<int> banknotesCount) {
        for (int i = 0; i < banknotesCount.size(); ++i) {
            cnt[i] += banknotesCount[i];
        }
    }

    vector<int> withdraw(int amount) {
        vector<int> ans(m);
        for (int i = m - 1; ~i; --i) {
            ans[i] = min(1ll * amount / d[i], cnt[i]);
            amount -= ans[i] * d[i];
        }
        if (amount > 0) {
            return {-1};
        }
        for (int i = 0; i < m; ++i) {
            cnt[i] -= ans[i];
        }
        return ans;
    }

private:
    static constexpr int d[5] = {20, 50, 100, 200, 500};
    static constexpr int m = size(d);
    long long cnt[m] = {0};
};

/**
 * Your ATM object will be instantiated and called as such:
 * ATM* obj = new ATM();
 * obj->deposit(banknotesCount);
 * vector<int> param_2 = obj->withdraw(amount);
 */

Go

var d = [...]int{20, 50, 100, 200, 500}

const m = len(d)

type ATM [m]int

func Constructor() ATM {
	return ATM{}
}

func (this *ATM) Deposit(banknotesCount []int) {
	for i, x := range banknotesCount {
		this[i] += x
	}
}

func (this *ATM) Withdraw(amount int) []int {
	ans := make([]int, m)
	for i := m - 1; i >= 0; i-- {
		ans[i] = min(amount/d[i], this[i])
		amount -= ans[i] * d[i]
	}
	if amount > 0 {
		return []int{-1}
	}
	for i, x := range ans {
		this[i] -= x
	}
	return ans
}

/**
 * Your ATM object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Deposit(banknotesCount);
 * param_2 := obj.Withdraw(amount);
 */

TypeScript

const d: number[] = [20, 50, 100, 200, 500];
const m = d.length;

class ATM {
    private cnt: number[];

    constructor() {
        this.cnt = Array(m).fill(0);
    }

    deposit(banknotesCount: number[]): void {
        for (let i = 0; i < banknotesCount.length; ++i) {
            this.cnt[i] += banknotesCount[i];
        }
    }

    withdraw(amount: number): number[] {
        const ans: number[] = Array(m).fill(0);
        for (let i = m - 1; i >= 0; --i) {
            ans[i] = Math.min(Math.floor(amount / d[i]), this.cnt[i]);
            amount -= ans[i] * d[i];
        }
        if (amount > 0) {
            return [-1];
        }
        for (let i = 0; i < m; ++i) {
            this.cnt[i] -= ans[i];
        }
        return ans;
    }
}

/**
 * Your ATM object will be instantiated and called as such:
 * var obj = new ATM()
 * obj.deposit(banknotesCount)
 * var param_2 = obj.withdraw(amount)
 */