Table of Contents
Design an ATM Machine
- There is an ATM machine that stores banknotes of
5denominations:20,50,100,200, and500dollars. - 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
$300and there are2$50banknotes,1$100banknote, and1$200banknote, then the machine will use the$100and$200banknotes. - However, if you try to withdraw
$600and there are3$200banknotes and1$500banknote, then the withdraw request will be rejected because the machine will first try to use the$500banknote and then be unable to use banknotes to complete the remaining$100. Note that the machine is not allowed to use the$200banknotes instead of the$500banknote.
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 length5of 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 == 50 <= banknotesCount[i] <= 1091 <= amount <= 109- At most
5000calls in total will be made towithdrawanddeposit. - At least one call will be made to each function
withdrawanddeposit. - Sum of
banknotesCount[i]in all deposits doesn’t exceed109
Golang Code
/**
* Your ATM object will be instantiated and called as such:
* obj := Constructor();
* obj.Deposit(banknotesCount);
* param_2 := obj.Withdraw(amount);
*/
type ATM struct {
arr []int
denominations [5]int
}
func Constructor() ATM {
return ATM{
arr: make([]int, 5),
denominations: [5]int{20, 50, 100, 200, 500},
}
}
func (this *ATM) Deposit(banknotesCount []int) {
for i := 0; i < len(banknotesCount); i++ {
this.arr[i] += banknotesCount[i]
}
}
func (this *ATM) Withdraw(amount int) []int {
result := make([]int, 5)
remainingAmt := amount
for i := len(this.arr) - 1; i >= 0 && remainingAmt > 0; i-- {
if this.arr[i] > 0 {
result[i] = min(this.arr[i], remainingAmt/this.denominations[i])
remainingAmt = remainingAmt - this.denominations[i]*result[i]
}
}
if remainingAmt > 0 {
return []int{-1}
}
for i := 0; i < len(this.arr); i++ {
this.arr[i] -= result[i]
}
return result
}Output
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]]
Please visit https: https://codeandalgo.com for more such contents.
Leave a Reply