Greedy 1 loop vs recursion||40ms Beats 99.76%
Intuition\n Describe your first thoughts on how to solve this problem. \ncount \$5, \$10 as possible returning change for bills. When b=20, the greedy algorithm
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\ncount \\$5, \\$10 as possible returning change for bills. When b=20, the greedy algorithm maintains the checking order. Give back \\$10 first,  keep \\$5  as possible and do not change the checking order, otherwise it will not work.\n\n2nd approach uses recursion which is more concise.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n[Please Turn English subtitles if necessary]\n[https://youtu.be/nuOhP6F6MYc?si=sVMDgrCt5S3EXMRE](https://youtu.be/nuOhP6F6MYc?si=sVMDgrCt5S3EXMRE)\n1. Only \\$5, \\$10 need to be counted\n2. Use a loop to transverse & deal with 3 different cases\n3. Case of 5, cnt5+=1\n4. Case of 10, if cnt5>0: cnt5-=1, cnt10+=1 else return False\n5. Case of 20: 3 possiblities: Greedy algorithm keeps the checking order, never change the checking order otherwise it will not work\n```\nif (cnt10>0 && cnt5>0) cnt10--, cnt5--;\nelse if (cnt5>2) cnt5-=3;\nelse return 0;\n```\n6. 2nd approach is a recursive code; add some extra parameter to keep the code concise: `int i=0, int cnt5=0, int cnt10=0`\n# Testcase for checking Greedy Algorithm by real RUN\nConsider the testcase bills=`[5, 5, 5, 5, 10, 20, 10]`\nIf the checking order in case of b=20 is changed, it will be wrong.\nProcceed the 1st C++ by adding some output\n```\ncnt5=0, cnt10=0: Receive $5\ncnt5=1, cnt10=0: Receive $5\ncnt5=2, cnt10=0: Receive $5\ncnt5=3, cnt10=0: Receive $5\ncnt5=4, cnt10=0: Recieve $10, give back $5\ncnt5=3, cnt10=1: Receive $20, give back $5, $10\ncnt5=2, cnt10=0: Recieve $10, give back $5\n=>answer is correct\n```\nWhat if changing the order by giving back ` 3 $ 5 $then $ 10 + $ 5`?\n```\ncnt5=0, cnt10=0: Receive $5\ncnt5=1, cnt10=0: Receive $5\ncnt5=2, cnt10=0: Receive $5\ncnt5=3, cnt10=0: Receive $5\ncnt5=4, cnt10=0: Recieve $10, give back $5\ncnt5=3, cnt10=1: Receive $20, give back 3 $5\ncnt5=0, cnt10=1: Not enough change\n=>answer is wrong\n```\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$\nrecursion:$O(n)$\n# Code||C++40ms Beats 99.76%\n```\nclass Solution {\npublic:\n    static bool lemonadeChange(vector<int>& bills) {\n        int cnt5=0, cnt10=0;\n        for(int b: bills){\n            switch(b){\n                case 5: \n                    cnt5++; \n                    break;\n                case 10: \n                    if (cnt5>0) cnt5--, cnt10++;\n                    else return 0;\n                    break;\n                case 20:\n                    if (cnt10>0 && cnt5>0) cnt10--, cnt5--;\n                    else if (cnt5>2) cnt5-=3;\n                    else return 0;\n                    break;\n            }\n        }\n        return 1;\n    }\n};\n\n\n \nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n# Python code done in video\n```\nclass Solution:\n    def lemonadeChange(self, bills: List[int]) -> bool:\n        cnt5, cnt10=0, 0\n        for b in bills:\n            if b==5: cnt5+=1\n            elif b==10:\n                if cnt5>0:\n                    cnt5-=1\n                    cnt10+=1\n                else:\n                    return False\n            else:\n                if cnt10>0 and cnt5>0:\n                    cnt10-=1\n                    cnt5-=1\n                elif cnt5>2: cnt5-=3\n                else: return False\n        return True\n        \n```\n# C++ recursion||65ms Beats 83.80%\n```\nclass Solution {\npublic:\n    static bool lemonadeChange(vector<int>& bills, int i=0, int cnt5=0, int cnt10=0) {\n        if (i==bills.size()) return cnt5>=0&&cnt10>=0;// base case\n        if (cnt5<0 || cnt10<0 ) return 0;\n        int b=bills[i];\n        if (b==5) return lemonadeChange(bills, i+1, cnt5+1, cnt10);\n        if (b==10) return lemonadeChange(bills, i+1, cnt5-1, cnt10+1);\n        if (b==20 && cnt10>0) return lemonadeChange(bills, i+1, cnt5-1, cnt10-1);\n        else return lemonadeChange(bills, i+1, cnt5-3, cnt10);\n    }\n};\n```
['Array', 'Greedy', 'Recursion', 'C++', 'Python3']