{"id":9659,"date":"2022-04-16T22:46:46","date_gmt":"2022-04-17T05:46:46","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9659"},"modified":"2022-04-16T22:47:26","modified_gmt":"2022-04-17T05:47:26","slug":"leetcode-2241-design-an-atm-machine","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/desgin\/leetcode-2241-design-an-atm-machine\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2241. Design an ATM Machine"},"content":{"rendered":"\n<p>There is an ATM machine that stores banknotes of&nbsp;<code>5<\/code>&nbsp;denominations:&nbsp;<code>20<\/code>,&nbsp;<code>50<\/code>,&nbsp;<code>100<\/code>,&nbsp;<code>200<\/code>, and&nbsp;<code>500<\/code>&nbsp;dollars. Initially the ATM is empty. The user can use the machine to deposit or withdraw any amount of money.<\/p>\n\n\n\n<p>When withdrawing, the machine prioritizes using banknotes of&nbsp;<strong>larger<\/strong>&nbsp;values.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example, if you want to withdraw&nbsp;<code>$300<\/code>&nbsp;and there are&nbsp;<code>2<\/code>&nbsp;<code>$50<\/code>&nbsp;banknotes,&nbsp;<code>1<\/code>&nbsp;<code>$100<\/code>&nbsp;banknote, and&nbsp;<code>1<\/code>&nbsp;<code>$200<\/code>&nbsp;banknote, then the machine will use the&nbsp;<code>$100<\/code>&nbsp;and&nbsp;<code>$200<\/code>&nbsp;banknotes.<\/li><li>However, if you try to withdraw&nbsp;<code>$600<\/code>&nbsp;and there are&nbsp;<code>3<\/code>&nbsp;<code>$200<\/code>&nbsp;banknotes and&nbsp;<code>1<\/code>&nbsp;<code>$500<\/code>&nbsp;banknote, then the withdraw request will be rejected because the machine will first try to use the&nbsp;<code>$500<\/code>&nbsp;banknote and then be unable to use banknotes to complete the remaining&nbsp;<code>$100<\/code>. Note that the machine is&nbsp;<strong>not<\/strong>&nbsp;allowed to use the&nbsp;<code>$200<\/code>&nbsp;banknotes instead of the&nbsp;<code>$500<\/code>&nbsp;banknote.<\/li><\/ul>\n\n\n\n<p>Implement the ATM class:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>ATM()<\/code>&nbsp;Initializes the ATM object.<\/li><li><code>void deposit(int[] banknotesCount)<\/code>&nbsp;Deposits new banknotes in the order&nbsp;<code>$20<\/code>,&nbsp;<code>$50<\/code>,&nbsp;<code>$100<\/code>,&nbsp;<code>$200<\/code>, and&nbsp;<code>$500<\/code>.<\/li><li><code>int[] withdraw(int amount)<\/code>&nbsp;Returns an array of length&nbsp;<code>5<\/code>&nbsp;of the number of banknotes that will be handed to the user in the order&nbsp;<code>$20<\/code>,&nbsp;<code>$50<\/code>,&nbsp;<code>$100<\/code>,&nbsp;<code>$200<\/code>, and&nbsp;<code>$500<\/code>, and update the number of banknotes in the ATM after withdrawing. Returns&nbsp;<code>[-1]<\/code>&nbsp;if it is not possible (do&nbsp;<strong>not<\/strong>&nbsp;withdraw any banknotes in this case).<\/li><\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input<\/strong>\n[\"ATM\", \"deposit\", \"withdraw\", \"deposit\", \"withdraw\", \"withdraw\"]\n[[], [[0,0,1,2,1]], [600], [[0,1,0,1,1]], [600], [550]]\n<strong>Output<\/strong>\n[null, null, [0,0,1,0,1], null, [-1], [0,1,0,0,1]]\n\n<strong>Explanation<\/strong>\nATM atm = new ATM();\natm.deposit([0,0,1,2,1]); \/\/ Deposits 1 $100 banknote, 2 $200 banknotes,\n                          \/\/ and 1 $500 banknote.\natm.withdraw(600);        \/\/ Returns [0,0,1,0,1]. The machine uses 1 $100 banknote\n                          \/\/ and 1 $500 banknote. The banknotes left over in the\n                          \/\/ machine are [0,0,0,2,0].\natm.deposit([0,1,0,1,1]); \/\/ Deposits 1 $50, $200, and $500 banknote.\n                          \/\/ The banknotes in the machine are now [0,1,0,3,1].\natm.withdraw(600);        \/\/ Returns [-1]. The machine will try to use a $500 banknote\n                          \/\/ and then be unable to complete the remaining $100,\n                          \/\/ so the withdraw request will be rejected.\n                          \/\/ Since the request is rejected, the number of banknotes\n                          \/\/ in the machine is not modified.\natm.withdraw(550);        \/\/ Returns [0,1,0,0,1]. The machine uses 1 $50 banknote\n                          \/\/ and 1 $500 banknote.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>banknotesCount.length == 5<\/code><\/li><li><code>0 &lt;= banknotesCount[i] &lt;= 10<sup>9<\/sup><\/code><\/li><li><code>1 &lt;= amount &lt;= 10<sup>9<\/sup><\/code><\/li><li>At most&nbsp;<code>5000<\/code>&nbsp;calls&nbsp;<strong>in total<\/strong>&nbsp;will be made to&nbsp;<code>withdraw<\/code>&nbsp;and&nbsp;<code>deposit<\/code>.<\/li><li>At least&nbsp;<strong>one<\/strong>&nbsp;call will be made to each function&nbsp;<code>withdraw<\/code>&nbsp;and&nbsp;<code>deposit<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution:<\/strong><\/h2>\n\n\n\n<p>Follow the rules. Note: total count can be very large, use long instead.<\/p>\n\n\n\n<p>Time complexity: O(1)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nconstexpr int kNotes = 5;\nconstexpr long notes[kNotes] = {20, 50, 100, 200, 500};\n\nclass ATM {\npublic:\n  ATM(): counts(kNotes) {}\n\n  void deposit(vector<int> banknotesCount) {\n    for (int i = 0; i < kNotes; ++i)\n      counts[i] += banknotesCount[i];\n  }\n\n  vector<int> withdraw(int amount) {\n    vector<int> ans(kNotes);\n    vector<long> tmp(counts);\n    for (int i = kNotes - 1; i >= 0; --i)\n      if (amount >= notes[i]) {\n        int c = min(counts[i], amount \/ notes[i]);\n        ans[i] = c;\n        amount -= c * notes[i];\n        tmp[i] -= c;\n      }\n    if (amount != 0) return {-1};\n    counts.swap(tmp);\n    return ans;\n  }\nprivate:\n  vector<long> counts;  \n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>There is an ATM machine that stores banknotes of&nbsp;5&nbsp;denominations:&nbsp;20,&nbsp;50,&nbsp;100,&nbsp;200, and&nbsp;500&nbsp;dollars. Initially the ATM is empty. The user can use the machine to deposit or withdraw&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[340],"tags":[251,177],"class_list":["post-9659","post","type-post","status-publish","format-standard","hentry","category-desgin","tag-design","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9659","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9659"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9659\/revisions"}],"predecessor-version":[{"id":9661,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9659\/revisions\/9661"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9659"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9659"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9659"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}