DCC-15 AUGUST 2024|| GREEDY
Problem Understanding and Intuition:\n\nThe problem "Lemonade Change" is about a lemonade stand where each lemonade costs $5. The customers pay with $5, $10, or
### Problem Understanding and Intuition:\n\nThe problem "Lemonade Change" is about a lemonade stand where each lemonade costs $5. The customers pay with $5, $10, or $20 bills. The goal is to determine whether the seller can provide the correct change to each customer in the order they arrive.\n\n### Approach:\n\n1. **Tracking Bills:**\n   - We need to keep track of the number of $5, $10, and $20 bills we have since we need these to give back the correct change.\n   - We use three variables: `five`, `ten`, and `twenty` to count the number of $5, $10, and $20 bills, respectively.\n\n2. **Processing Each Bill:**\n   - If the customer pays with a $5 bill, no change is needed, so we simply increase the count of `five`.\n   - If the customer pays with a $10 bill, we need to give back $5 in change. We check if we have at least one $5 bill:\n     - If yes, we decrease the `five` count and increase the `ten` count.\n     - If no, we return `false` because we cannot provide the correct change.\n   - If the customer pays with a $20 bill, we need to give back $15 in change. The optimal way to do this is:\n     - First, try to use one $10 bill and one $5 bill.\n     - If we don\'t have a $10 bill, we must use three $5 bills.\n     - If neither option is available, we return `false` because we cannot provide the correct change.\n\n3. **Complexity Consideration:**\n   - The approach involves iterating through each bill in the array and making constant-time operations (checking and updating the counts).\n   - **Time Complexity:** `O(n)`, where `n` is the length of the `bills` array.\n   - **Space Complexity:** `O(1)` since we\'re only using a fixed number of variables to store the counts of the bills.\n\n# Code\n```\nclass Solution {\n    public boolean lemonadeChange(int[] bills) {\n        int five = 0;\n        int ten =0;\n        <!-- int twenty = 0; -->\n        int coins=0;\n        for(int i=0;i<bills.length;i++){\n            if(bills[i]==5) five++;\n            if(bills[i]==10) ten++;\n            <!-- if(bills[i]==20) twenty++; -->\n            int change = bills[i]-5;\n            if(change==0) continue;\n            <!-- while(change>=20 && twenty>0){\n                change-=20;\n                twenty--;\n            } -->\n             while(change>=10 && ten>0){\n                change-=10;\n                ten--;\n            }\n             while(change>=5 && five>0){\n                change-=5;\n                five--;\n            }\n            if(change!=0) return false;\n        }\n        return true;\n    }\n}\n```
['Greedy', 'Java']