2241. Design an ATM Machine Medium

1/**
2 * [2241] Design an ATM Machine
3 *
4 * 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.
5 * When withdrawing, the machine prioritizes using banknotes of larger values.
6 *
7 * 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.
8 * 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.
9 *
10 * Implement the ATM class:
11 *
12 * ATM() Initializes the ATM object.
13 * void deposit(int[] banknotesCount) Deposits new banknotes in the order $20, $50, $100, $200, and $500.
14 * 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).
15 *
16 *  
17 * Example 1:
18 *
19 * Input
20 * ["ATM", "deposit", "withdraw", "deposit", "withdraw", "withdraw"]
21 * [[], [[0,0,1,2,1]], [600], [[0,1,0,1,1]], [600], [550]]
22 * Output
23 * [null, null, [0,0,1,0,1], null, [-1], [0,1,0,0,1]]
24 * Explanation
25 * ATM atm = new ATM();
26 * atm.deposit([0,0,1,2,1]); // Deposits 1 $100 banknote, 2 $200 banknotes,
27 *                           // and 1 $500 banknote.
28 * atm.withdraw(600);        // Returns [0,0,1,0,1]. The machine uses 1 $100 banknote
29 *                           // and 1 $500 banknote. The banknotes left over in the
30 *                           // machine are [0,0,0,2,0].
31 * atm.deposit([0,1,0,1,1]); // Deposits 1 $50, $200, and $500 banknote.
32 *                           // The banknotes in the machine are now [0,1,0,3,1].
33 * atm.withdraw(600);        // Returns [-1]. The machine will try to use a $500 banknote
34 *                           // and then be unable to complete the remaining $100,
35 *                           // so the withdraw request will be rejected.
36 *                           // Since the request is rejected, the number of banknotes
37 *                           // in the machine is not modified.
38 * atm.withdraw(550);        // Returns [0,1,0,0,1]. The machine uses 1 $50 banknote
39 *                           // and 1 $500 banknote.
40 *  
41 * Constraints:
42 *
43 * banknotesCount.length == 5
44 * 0 <= banknotesCount[i] <= 10^9
45 * 1 <= amount <= 10^9
46 * At most 5000 calls in total will be made to withdraw and deposit.
47 * At least one call will be made to each function withdraw and deposit.
48 *
49 */
50pub struct Solution {}
51
52// problem: https://leetcode.com/problems/design-an-atm-machine/
53// discuss: https://leetcode.com/problems/design-an-atm-machine/discuss/?currentPage=1&orderBy=most_votes&query=
54
55// submission codes start here
56
57struct ATM {
58    store: Vec<i64>,
59}
60
61/**
62 * `&self` means the method takes an immutable reference.
63 * If you need a mutable reference, change it to `&mut self` instead.
64 */
65use std::cmp;
66impl ATM {
67    const DENO: [i32; 5] = [20, 50, 100, 200, 500];
68    fn new() -> Self {
69        ATM { store: vec![0; 5] }
70    }
71
72    fn deposit(&mut self, banknotes_count: Vec<i32>) {
73        for (i, v) in banknotes_count.iter().enumerate() {
74            self.store[i] += *v as i64;
75        }
76    }
77
78    fn withdraw(&mut self, amount: i32) -> Vec<i32> {
79        let mut remains = amount as i64;
80        let mut result = vec![0; 5];
81        for i in (0..5).rev() {
82            let d = cmp::min(self.store[i], remains / Self::DENO[i] as i64);
83            remains -= d * Self::DENO[i] as i64;
84            result[i] += d;
85        }
86        if remains != 0 {
87            vec![-1]
88        } else {
89            for i in 0..5 {
90                self.store[i] -= result[i];
91            }
92            result.iter().map(|x| *x as i32).collect()
93        }
94    }
95
96    fn print(&self) {
97        println!("Store {:#?}", self.store);
98    }
99}
100
101/**
102 * Your ATM object will be instantiated and called as such:
103 * let obj = ATM::new();
104 * obj.deposit(banknotesCount);
105 * let ret_2: Vec<i32> = obj.withdraw(amount);
106 */
107
108// submission codes end
109
110#[cfg(test)]
111mod tests {
112    use super::*;
113
114    #[test]
115    fn test_2241() {
116        let mut atm = ATM::new();
117        atm.print();
118        atm.deposit(vec![0, 0, 1, 2, 1]);
119        atm.print();
120        assert_eq!(atm.withdraw(600), vec![0, 0, 1, 0, 1]);
121        atm.print();
122        atm.deposit(vec![0, 1, 0, 1, 1]);
123        atm.print();
124        assert_eq!(atm.withdraw(600), vec![-1]);
125        atm.print();
126        assert_eq!(atm.withdraw(550), vec![0, 1, 0, 0, 1]);
127    }
128}
129