Lemonade Change (Easy Explanation - 100 % beats)  - 1ms
Intuition\n Describe your first thoughts on how to solve this problem. \n- The lemonade costs 5 dollars,the customer might pay either 5,10 or 20 dollars.If they
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- The lemonade costs 5 dollars,the customer might pay either 5,10 or 20 dollars.If they pay 10 dollars,we have to give them a change of 5 dollars and if the customer pay 20 dollars,we have to pay them a change of 15 dollars, ie. either 3 5dollars or 1 5dollars and 1 10dollars. \n\n- Initially we might not have any change,so if the first customer gives 10 or 20 dollars,we might not able to provide them with change,hence we should return false.\n\n- If we might able to provide all customer with the correct change,we should return true.Otherwise,we may return false.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**Keep track of available change**:\n\n-The available change may be keep track in terms of number 10 dollars and 5 dollars available,this might help us to determine whether we can provide a customer a change or not.So initialize the two variables five and ten as 0.\n\n**Condition Checking**:\n\n**Customer pays exactly 5 dollars**:\n\n-There is no need of providing any change,so we can increment the five to 1.So that it can be useful later for providing change.\n\n**Customer pays 10 dollars**:\n\n-If the customer pays 10 dollars,the actual cost of the lemonade was 5,So the change we have to give is 10 - 5 = 5 dollars.\n    \n     Change amount = customer paid amount - lemonade cost (5 dollars)\n    \n-Hence this is the time to check if the 5 dollars is available to him or not to provide the customer with the change.So we check the tracking variable five > 0,hence we decrement the count of five and increment the count of ten.\n    \n**Customer pays 20 dollars**:\n\n-If the customer pays 20 dollars,the change we have to give to the customer is 15 dollars.\n\n-It can be of any form,that can be 1 10dollars and 1 5dollars or 3 5dollars.\n\n-So can check the availability of that by checking if ten>0 and five > 0,then we can provide the customer with 1 10dollar and 1 5dollar or we can check if five >= 3,if so we can provide customer with 3 five dollars.\n\n-If both the ways are not possible,then we may not able to provide customer with the change,So we return false.\n\n# Complexity\n- Time complexity: **O(n)**\n    n -> number of elements in the bill array.\n- The program iterates through bill array only once\n- Each operation inside the loop takes constant time **O(1)**\n\nHence Overall Time Complexity is **O(n)**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:**O(1)**\n- The program takes constant amount of extra space : two integer variables(ten and five) to keep track of 10 and 5 dollars respectively.\n- No additional space is used that grows with input size.\n\nHence Overall Space Complexity is **O(1)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public boolean lemonadeChange(int[] bills) {\n        int five = 0;\n        int ten = 0;\n        \n        for (int bill : bills) {\n            if (bill == 5) {\n                five++;\n            } else if (bill == 10) {\n                if (five > 0) {\n                    five--;\n                    ten++;\n                } else {\n                    return false;\n                }\n            } else { // bill == 20\n                if (ten > 0 && five > 0) {\n                    ten--;\n                    five--;\n                } else if (five >= 3) {\n                    five -= 3;\n                } else {\n                    return false;\n                }\n            }\n        }\n        \n        return true;\n    }\n}\n```
['Array', 'Greedy', 'Java']