O(n) | Stack | Greedy | Java | C++ | Python | Go | Rust | JavaScript
\n# Approach 1\n### Intuition\n\nImagine you\u2019re running a lemonade stand on a hot summer day. The lemonade is priced at 5 dollars per cup, and customers ar
\n# Approach 1\n### Intuition\n\nImagine you\u2019re running a lemonade stand on a hot summer day. The lemonade is priced at 5 dollars per cup, and customers are lining up to quench their thirst. However, not everyone has exact change, and you start the day with an empty cash box. Your challenge is to determine if you can successfully operate your stand throughout the day, providing correct change to every customer, given the sequence of bills they\u2019ll present.\n\nThe tricky part is, we start with no change in our pocket. So we\'ve got to figure out if we can make change for everyone as they come up to buy lemonade. If we can\'t make change even once, we\'re in trouble and have to close up shop.\n\nWhen I first looked at this problem, I thought, this is all about keeping track of the money we have and making smart decisions about how to give change. It\'s like a puzzle where each customer is a new piece, and we have to fit it in just right.\n\nThe key here is to think ahead. We need to hold onto smaller bills when we can, because they\'re going to be super useful for making change later. It\'s kind of like playing chess - you\'ve got to think a few moves ahead.\n\n## Approach\n### Step 1: State Representation\n\nThe first decision we need to make is how to represent the state of our cash box. We could use a variety of data structures, but let\'s consider what information is truly necessary:\n\n1. We need to know how many 5 dollar bills we have.\n2. We need to know how many 10 dollar bills we have.\n3. Do we need to keep track of 20 dollar bills?\n\nAfter careful consideration, we realize that we don\'t need to keep track of 20 dollar bills. Why? Because we never use them to make change. Once we receive a 20 dollar bill, it stays in our cash box and doesn\'t affect our ability to make change for future customers.\n\nSo, our state can be represented by just two integers:\n- `fives`: The number of 5 dollar bills we have.\n- `tens`: The number of 10 dollar bills we have.\n\nThis simple state representation is sufficient to solve the problem and leads to an efficient solution with minimal space complexity.\n\n### Step 2: Processing Transactions\n\nNow that we have our state representation, let\'s consider how to process each transaction. We\'ll need to handle three cases:\n\n1. Customer pays with a 5 dollar bill:\n   This is the simplest case. We don\'t need to give any change, so we just add the 5 dollar bill to our count of fives.\n\n2. Customer pays with a 10 dollar bill:\n   We need to give 5 dollars in change. To do this, we need at least one 5 dollar bill. If we have one, we can make the change by decrementing our count of fives and incrementing our count of tens. If we don\'t have a 5 dollar bill, we can\'t make change, and we need to close the stand.\n\n3. Customer pays with a 20 dollar bill:\n   This is the most complex case. We need to give 15 dollars in change. We have two options:\n   a. Give one 10 dollar bill and one 5 dollar bill.\n   b. Give three 5 dollar bills.\n\n   We prefer option (a) when possible because it allows us to keep more 5 dollar bills, which are more flexible for making change. If we can\'t do (a), we try (b). If we can\'t do either, we need to close the stand.\n\n### Step 3: The Greedy Choice\n\nIn the case of a 20 dollar bill, we\'re making a greedy choice by preferring to give a 10 dollar bill and a 5 dollar bill as change. This choice is greedy because it\'s the best option for our current transaction (it leaves us with more 5 dollar bills), but we\'re not considering future transactions.\n\nWhy is this greedy choice actually optimal? Because 5 dollar bills are the most versatile for making change. By keeping as many 5 dollar bills as possible, we maximize our ability to make change for future transactions.\n\n### Step 4: Implementing the Algorithm\n\nNow, let\'s talk about how we\'re going to tackle this problem step by step.\n\n1. First things first, we\'re going to create a `LemonadeStand` class. This class is going to be our lemonade stand in code form. It\'s going to keep track of all our money and handle all our transactions.\n\n2. Inside this class, we\'re going to have two important variables:\n   - `fives`: This is going to count how many 5 dollar bills we have.\n   - `tens`: This is going to count how many 10 dollar bills we have.\n\n   Notice we don\'t bother counting 20 dollar bills. Why? Because we never use them to make change. They just sit in our cash box looking pretty.\n\n3. Now, we\'re going to create a method called `canProvideChange`. This method is going to take an array of all the bills our customers are going to give us throughout the day. It\'s like being able to see into the future and know exactly what everyone\'s going to pay with.\n\n4. Inside `canProvideChange`, we\'re going to go through each bill one by one. For each bill, we\'re going to call another method called `processTransaction`. This method is where the magic happens - it\'s going to handle each individual sale.\n\n5. Let\'s break down `processTransaction`:\n   - If someone gives us a 5 dollar bill, awesome! We just add it to our count of fives and move on.\n   - If someone gives us a 10 dollar bill, we need to give them 5 dollars change. So we check if we have any 5 dollar bills. If we do, great! We give them one 5 dollar bill (by decreasing our `fives` count) and add their 10 to our `tens` count. If we don\'t have a 5 dollar bill, uh-oh! We can\'t make change, so we return `false`.\n   - If someone gives us a 20 dollar bill, things get a bit more complicated. We need to give them 15 dollars in change. For this, we call another method called `provideChangeFor20`.\n\n6. In `provideChangeFor20`, we have two options:\n   - Option 1: Give them one 10 dollar bill and one 5 dollar bill. This is our preferred option because it lets us hold onto more 5 dollar bills, which are super useful.\n   - Option 2: If we don\'t have a 10 dollar bill (or not enough 5 dollar bills), we can give them three 5 dollar bills.\n   - If we can\'t do either of these, we\'re out of luck and have to return `false`.\n\n7. If at any point during all these transactions we can\'t make change (meaning `processTransaction` returns `false`), we immediately stop and say we can\'t provide change for everyone (by returning `false` from `canProvideChange`).\n\n8. If we make it through all the transactions without any problems, hooray! We return `true` because we successfully gave everyone their lemonade and correct change.\n\nIn this approach We\'re always trying to make the best decision right now, without worrying too much about the future. But because we prefer to give 10 dollar bills as change when we can, we\'re actually setting ourselves up for success in the future too.\n\n### Complexity\n\nNow, let\'s talk about how efficient this solution is.\n\n **Time complexity: O(n)**\n  Here\'s why: We go through each bill in the input array exactly once. No matter how many bills there are, we only look at each one a single time. So if there are n bills, we do about n operations. This is what we call linear time complexity, or O(n).\n\n- The `canProvideChange` method goes through each bill once: O(n)\n- For each bill, we call `processTransaction`, which is O(1) because it just does a few simple operations\n- `provideChangeFor20` is also O(1) for the same reason\n- So, overall, we\'re doing O(1) work n times, which gives us O(n)\n\n **Space complexity: O(1)**\n  This is the really cool part. No matter how many customers we have or how many bills they give us, we only ever use two variables to keep track of our money (`fives` and `tens`). We don\'t create any new data structures that grow with the input size. This is what we call constant space complexity, or O(1).\n\n- We only use two integer variables (`fives` and `tens`) regardless of input size\n- We don\'t create any arrays, lists, or other data structures that grow with input\n- So our space usage is constant, giving us O(1)\n\n\n\n\n\n### Code\n```Java []\nclass LemonadeStand {\n    private int fives = 0;\n    private int tens = 0;\n\n    public boolean canProvideChange(int[] customerBills) {\n        for (int bill : customerBills) {\n            if (!processTransaction(bill)) {\n                return false;\n            }\n        }\n        return true;\n    }\n\n    private boolean processTransaction(int bill) {\n        switch (bill) {\n            case 5:\n                fives++;\n                return true;\n            case 10:\n                if (fives == 0) return false;\n                fives--;\n                tens++;\n                return true;\n            case 20:\n                return provideChangeFor20();\n            default:\n                throw new IllegalArgumentException("Invalid bill: " + bill);\n        }\n    }\n\n    private boolean provideChangeFor20() {\n        if (tens > 0 && fives > 0) {\n            tens--;\n            fives--;\n        } else if (fives >= 3) {\n            fives -= 3;\n        } else {\n            return false;\n        }\n        return true;\n    }\n}\n\n\nclass Solution {\n    public boolean lemonadeChange(int[] bills) {\n        return new LemonadeStand().canProvideChange(bills);\n    }\n}\n```\n```C++ []\nclass LemonadeStand {\nprivate:\n    int fives = 0;\n    int tens = 0;\n\n    bool processTransaction(int bill) {\n        switch (bill) {\n            case 5:\n                fives++;\n                return true;\n            case 10:\n                if (fives == 0) return false;\n                fives--;\n                tens++;\n                return true;\n            case 20:\n                return provideChangeFor20();\n            default:\n                throw std::invalid_argument("Invalid bill");\n        }\n    }\n\n    bool provideChangeFor20() {\n        if (tens > 0 && fives > 0) {\n            tens--;\n            fives--;\n        } else if (fives >= 3) {\n            fives -= 3;\n        } else {\n            return false;\n        }\n        return true;\n    }\n\npublic:\n    bool canProvideChange(std::vector<int>& bills) {\n        for (int bill : bills) {\n            if (!processTransaction(bill)) {\n                return false;\n            }\n        }\n        return true;\n    }\n};\n\nclass Solution {\npublic:\n    bool lemonadeChange(std::vector<int>& bills) {\n        return LemonadeStand().canProvideChange(bills);\n    }\n};\n```\n```Python []\nclass LemonadeStand:\n    def __init__(self):\n        self.fives = 0\n        self.tens = 0\n\n    def can_provide_change(self, bills):\n        for bill in bills:\n            if not self.process_transaction(bill):\n                return False\n        return True\n\n    def process_transaction(self, bill):\n        if bill == 5:\n            self.fives += 1\n            return True\n        elif bill == 10:\n            if self.fives == 0:\n                return False\n            self.fives -= 1\n            self.tens += 1\n            return True\n        elif bill == 20:\n            return self.provide_change_for_20()\n        else:\n            raise ValueError("Invalid bill")\n\n    def provide_change_for_20(self):\n        if self.tens > 0 and self.fives > 0:\n            self.tens -= 1\n            self.fives -= 1\n        elif self.fives >= 3:\n            self.fives -= 3\n        else:\n            return False\n        return True\n\nclass Solution:\n    def lemonadeChange(self, bills: List[int]) -> bool:\n        return LemonadeStand().can_provide_change(bills)\n```\n```Go []\npackage main\n\ntype LemonadeStand struct {\n    fives int\n    tens  int\n}\n\nfunc (ls *LemonadeStand) canProvideChange(bills []int) bool {\n    for _, bill := range bills {\n        if !ls.processTransaction(bill) {\n            return false\n        }\n    }\n    return true\n}\n\nfunc (ls *LemonadeStand) processTransaction(bill int) bool {\n    switch bill {\n    case 5:\n        ls.fives++\n        return true\n    case 10:\n        if ls.fives == 0 {\n            return false\n        }\n        ls.fives--\n        ls.tens++\n        return true\n    case 20:\n        return ls.provideChangeFor20()\n    default:\n        \n        return false\n    }\n}\n\nfunc (ls *LemonadeStand) provideChangeFor20() bool {\n    if ls.tens > 0 && ls.fives > 0 {\n        ls.tens--\n        ls.fives--\n    } else if ls.fives >= 3 {\n        ls.fives -= 3\n    } else {\n        return false\n    }\n    return true\n}\n\nfunc lemonadeChange(bills []int) bool {\n    stand := &LemonadeStand{}\n    return stand.canProvideChange(bills)\n}\n```\n```Rust []\nstruct LemonadeStand {\n    fives: i32,\n    tens: i32,\n}\n\nimpl LemonadeStand {\n    fn new() -> Self {\n        LemonadeStand { fives: 0, tens: 0 }\n    }\n\n    fn can_provide_change(&mut self, bills: Vec<i32>) -> bool {\n        for bill in bills {\n            if !self.process_transaction(bill) {\n                return false;\n            }\n        }\n        true\n    }\n\n    fn process_transaction(&mut self, bill: i32) -> bool {\n        match bill {\n            5 => {\n                self.fives += 1;\n                true\n            }\n            10 => {\n                if self.fives == 0 {\n                    return false;\n                }\n                self.fives -= 1;\n                self.tens += 1;\n                true\n            }\n            20 => self.provide_change_for_20(),\n            _ => false, \n        }\n    }\n\n    fn provide_change_for_20(&mut self) -> bool {\n        if self.tens > 0 && self.fives > 0 {\n            self.tens -= 1;\n            self.fives -= 1;\n        } else if self.fives >= 3 {\n            self.fives -= 3;\n        } else {\n            return false;\n        }\n        true\n    }\n}\n\n\n\nimpl Solution {\n    pub fn lemonade_change(bills: Vec<i32>) -> bool {\n        LemonadeStand::new().can_provide_change(bills)\n    }\n}\n```\n```JavaScript []\nclass LemonadeStand {\n    constructor() {\n        this.fives = 0;\n        this.tens = 0;\n    }\n\n    canProvideChange(bills) {\n        for (let bill of bills) {\n            if (!this.processTransaction(bill)) {\n                return false;\n            }\n        }\n        return true;\n    }\n\n    processTransaction(bill) {\n        switch (bill) {\n            case 5:\n                this.fives++;\n                return true;\n            case 10:\n                if (this.fives === 0) return false;\n                this.fives--;\n                this.tens++;\n                return true;\n            case 20:\n                return this.provideChangeFor20();\n            default:\n                throw new Error("Invalid bill");\n        }\n    }\n\n    provideChangeFor20() {\n        if (this.tens > 0 && this.fives > 0) {\n            this.tens--;\n            this.fives--;\n        } else if (this.fives >= 3) {\n            this.fives -= 3;\n        } else {\n            return false;\n        }\n        return true;\n    }\n}\n\n/**\n * @param {number[]} bills\n * @return {boolean}\n */\nvar lemonadeChange = function(bills) {\n    return new LemonadeStand().canProvideChange(bills);\n};\n\n```\n---\n# Approach 2\n\n\n\n### Intuition\n\nYou know how when you\'re dealing with cash, you sometimes stack bills of the same denomination together? That\'s essentially what we\'re doing here, but in code. Instead of just counting how many of each bill we have, we\'re actually keeping them in separate stacks.\n\nPicture this: You\'ve got two stacks of bills on your lemonade stand counter. One stack is for 5 dollar bills, and another for 10 dollar bills. Every time you get a new bill, you put it on top of the appropriate stack. When you need to make change, you take bills off the top of these stacks.\n\nThis stack idea came to me when I was thinking about how we handle money in real life. We don\'t just keep a mental count; we physically organize our cash. This approach mimics that real-world behavior more closely.\n\n### Approach\n \nLet\'s break down into more detail.\n\n1. **Initialize the Cash Box**\n\nWe start by setting up our virtual cash box. In the real world, we might have two compartments in our cash drawer - one for 5-dollar bills and another for 10-dollar bills. In our code, we\'ll represent these compartments as stacks.\n\n```\nfunction lemonadeChange(bills):\n    create empty stack fives\n    create empty stack tens\n```\n\nThese stacks will operate on the Last-In-First-Out (LIFO) principle, just like how you\'d naturally stack bills in a real cash box. The last bill you put in is the first one you\'d take out when making change.\n\n2. **Process Each Customer**\n\nNow, we\'ll go through each customer\'s payment one by one. We\'ll use a loop to iterate through the \'bills\' array.\n\n```\n    for each bill in bills:\n        if canMakeChange(bill):\n            continue\n        else:\n            return false\n```\n\nHere, we\'re checking if we can make change for each customer. If we can\'t make change for even one customer, we immediately return false because we\'ve failed our task.\n\n3. **Handling Different Bill Denominations**\n\nLet\'s break down the `canMakeChange` function:\n\n```\nfunction canMakeChange(bill):\n    if bill is 5:\n        push 5 onto fives stack\n        return true\n    else if bill is 10:\n        if fives is empty:\n            return false\n        pop from fives stack\n        push 10 onto tens stack\n        return true\n    else if bill is 20:\n        return makeChangeFor20()\n    else:\n        throw error "Invalid bill denomination"\n```\n\nLet\'s examine each case:\n\n- a) 5-dollar bill:\n   This is the simplest case. We don\'t need to make any change, we just add the 5-dollar bill to our fives stack. It\'s like saying, "Thanks for the exact change!" and putting the bill in our cash box.\n\n- b) 10-dollar bill:\n   Here\'s where it gets interesting. The customer is overpaying by 5 dollars, so we need to give them 5 dollars back. We first check if we have any 5-dollar bills. If we don\'t, we\'re in trouble - we can\'t make change, so we return false. If we do have a 5-dollar bill, we remove it from our fives stack (that\'s the \'pop\' operation) and give it to the customer. Then we add the 10-dollar bill to our tens stack.\n\n- c) 20-dollar bill:\n   This is the most complex case, so we\'ve separated it into its own function. Let\'s look at that next.\n\n4. **Making Change for a 20-dollar Bill**\n\nHere\'s where our stack approach really shines. We have two possible ways to make 15 dollars in change: one 10-dollar bill and one 5-dollar bill, or three 5-dollar bills. We\'ll try these options in order.\n\n```\nfunction makeChangeFor20():\n    if tens is not empty and fives is not empty:\n        pop from tens stack\n        pop from fives stack\n        return true\n    else if size of fives stack is at least 3:\n        pop from fives stack\n        pop from fives stack\n        pop from fives stack\n        return true\n    else:\n        return false\n```\n\nLet\'s break this down:\n\na) First, we check if we have both a 10-dollar bill and a 5-dollar bill. If we do, we use those to make change. We remove one bill from each stack.\n\nb) If we don\'t have that combination, we check if we have at least three 5-dollar bills. If we do, we use those, removing three bills from the fives stack.\n\nc) If we can\'t do either of these, we\'re out of luck. We can\'t make change, so we return false.\n\nThis approach mimics how you might actually make change in real life. You\'d first look for the larger bill to make change more quickly, and only break it down into smaller bills if you have to.\n\n5. **Completing the Transaction**\n\nIf we\'ve made it through all the customers without returning false, it means we successfully gave everyone correct change. So we return true at the end of our main function.\n\n```\n    return true  // We\'ve successfully served all customers\n```\n\n\n\n\n### Complexity\n\n\n\n- **Time complexity: O(n)**\n  We\'re still processing each customer exactly once, where n is the number of customers (or the length of the `bills` array). Each operation (pushing or popping from a stack) is O(1), so our overall time complexity remains linear.\n\n- **Space complexity: O(n)**\n  This is where our stack approach differs from the counter approach. In the worst case, if all customers pay with 5 dollar bills, we\'ll end up with a stack of n 5 dollar bills. So our space complexity is O(n).\n\n  However, it\'s worth noting that in practice, our space usage will often be much less than n. We\'re only storing 5 dollar and 10 dollar bills, and we\'re using them to make change as we go. So unless we have a long string of 5 dollar payments, our stacks won\'t grow too large.\n\n\n\n\n### Code\n\n\n \n```Java []\nclass Solution {\n    public boolean lemonadeChange(int[] bills) {\n        Stack<Integer> fives = new Stack<>();\n        Stack<Integer> tens = new Stack<>();\n        \n        for (int bill : bills) {\n            if (bill == 5) {\n                fives.push(5);\n            } else if (bill == 10) {\n                if (fives.isEmpty()) return false;\n                fives.pop();\n                tens.push(10);\n            } else if (bill == 20) {\n                if (!tens.isEmpty() && !fives.isEmpty()) {\n                    tens.pop();\n                    fives.pop();\n                } else if (fives.size() >= 3) {\n                    fives.pop();\n                    fives.pop();\n                    fives.pop();\n                } else {\n                    return false;\n                }\n            }\n        }\n        return true;\n    }\n}\n\n```\n\n```C++ []\nclass Solution {\npublic:\n    bool lemonadeChange(vector<int>& bills) {\n        int fives = 0, tens = 0;\n        for (int bill : bills) {\n            if (bill == 5) {\n                fives++;\n            } else if (bill == 10) {\n                if (fives == 0) return false;\n                fives--;\n                tens++;\n            } else { // bill == 20\n                if (tens > 0 && fives > 0) {\n                    tens--;\n                    fives--;\n                } else if (fives >= 3) {\n                    fives -= 3;\n                } else {\n                    return false;\n                }\n            }\n        }\n        return true;\n    }\n};\n```\n\n```Python []\nclass Solution:\n    def lemonadeChange(self, bills: List[int]) -> bool:\n        fives, tens = 0, 0\n        \n        for bill in bills:\n            if bill == 5:\n                fives += 1\n            elif bill == 10:\n                if fives == 0:\n                    return False\n                fives -= 1\n                tens += 1\n            elif bill == 20:\n                if tens > 0 and fives > 0:\n                    tens -= 1\n                    fives -= 1\n                elif fives >= 3:\n                    fives -= 3\n                else:\n                    return False\n            else:\n                return False  # Invalid bill\n        \n        return True\n\ns = Solution()\nwith open(\'user.out\', \'w\') as f:\n    for case in map(json.loads, stdin):\n        result = s.lemonadeChange(case)\n        f.write(f"{str(result).lower()}\\n")\n\nexit(0)\n```\n```Go []\nfunc lemonadeChange(bills []int) bool {\n    fives, tens := 0, 0\n    for _, bill := range bills {\n        if bill == 5 {\n            fives++\n        } else if bill == 10 {\n            if fives == 0 {\n                return false\n            }\n            fives--\n            tens++\n        } else { // bill == 20\n            if tens > 0 && fives > 0 {\n                tens--\n                fives--\n            } else if fives >= 3 {\n                fives -= 3\n            } else {\n                return false\n            }\n        }\n    }\n    return true\n}\n```\n\n```Rust []\nimpl Solution {\n    pub fn lemonade_change(bills: Vec<i32>) -> bool {\n        let mut fives = 0;\n        let mut tens = 0;\n        for bill in bills {\n            match bill {\n                5 => fives += 1,\n                10 => {\n                    if fives == 0 {\n                        return false;\n                    }\n                    fives -= 1;\n                    tens += 1;\n                }\n                20 => {\n                    if tens > 0 && fives > 0 {\n                        tens -= 1;\n                        fives -= 1;\n                    } else if fives >= 3 {\n                        fives -= 3;\n                    } else {\n                        return false;\n                    }\n                }\n                _ => unreachable!(),\n            }\n        }\n        true\n    }\n}\n```\n```JavaScript []\n/**\n * @param {number[]} bills\n * @return {boolean}\n */\nvar lemonadeChange = function(bills) {\n    let fives = 0, tens = 0;\n    for (let bill of bills) {\n        if (bill === 5) {\n            fives++;\n        } else if (bill === 10) {\n            if (fives === 0) return false;\n            fives--;\n            tens++;\n        } else { // bill === 20\n            if (tens > 0 && fives > 0) {\n                tens--;\n                fives--;\n            } else if (fives >= 3) {\n                fives -= 3;\n            } else {\n                return false;\n            }\n        }\n    }\n    return true;\n};\n```\n---\n# Approach 3\n### Intuition\n\nThe key insight is the realization that we can compress all the necessary information about our lemonade stand\'s state into a single integer. By using the binary nature of computer memory, we can efficiently pack two separate counters into one variable, allowing for rapid updates and checks.\n\n\nThe intuition here is that by using bitwise operations, we can perform multiple actions in a single operation, potentially speeding up our solution. Additionally, by keeping all our state in a single variable, we\'re optimizing for cache performance, which can lead to significant speed improvements on modern hardware.\n\n### Approach\n\nOur approach can be broken down into several key steps:\n\n1. **State Initialization:** We start with a single integer variable initialized to 0. This will store our entire lemonade stand state.\n\n2. **Processing Transactions:** We iterate through each bill in the input array, updating our state based on the bill\'s value:\n\n   - For a Dollar 5 bill, we increment the lower 16 bits of our state.\n   - For a Dollar 10 bill, we first check if we have a Dollar 5 to give as change. If not, we return false. Otherwise, we decrement the Dollar 5 count and increment the Dollar 10 count.\n   - For a Dollar 20 bill, we first try to give change using a Dollar 10 and a Dollar 5. If that\'s not possible, we try using three Dollar 5 bills. If neither option is possible, we return false.\n\n3. **State Updates:** We use bitwise operations to efficiently update our state:\n   - Adding to the Dollar 5 count is a simple increment.\n   - Adding to the Dollar 10 count involves adding 0x10000 to our state.\n   - Removing bills involves subtracting from our state.\n\n4. **State Checks:** We use bitwise AND operations to check our bill counts:\n   - AND with 0xFFFF checks the Dollar 5 count.\n   - AND with 0xFFFF0000 checks the Dollar 10 count.\n\n5. **Final Result:** If we successfully process all transactions, we return true. Otherwise, we return false at the point where we can\'t make change.\n\nThis approach allows us to handle all transactions efficiently, using minimal memory and leveraging fast bitwise operations.\n\n### Complexity\n\n- **Time complexity: O(n)**, where n is the number of bills in the input array. We process each bill exactly once, and each processing step takes constant time (bitwise operations are typically O(1) on modern hardware).\n\n- **Space complexity: O(1)**. We use only a single integer variable to store our state, regardless of the input size. This constant space usage is one of the major advantages of this approach.\n\n\n\n# Code\n```Java []\nclass Solution {\n    public boolean lemonadeChange(int[] bills) {\n        int state = 0;\n        \n        for (int bill : bills) {\n            if (bill == 5) {\n                state++;\n            } else if (bill == 10) {\n                if ((state & 0xFFFF) == 0) return false;\n                state--;\n                state += 0x10000;\n            } else { // bill == 20\n                if ((state & 0xFFFF0000) != 0 && (state & 0xFFFF) != 0) {\n                    state -= 0x10001;\n                } else if ((state & 0xFFFF) >= 3) {\n                    state -= 3;\n                } else {\n                    return false;\n                }\n            }\n        }\n        \n        return true;\n    }\n}\n\n```\n```C++ []\nclass Solution {\npublic:\n    bool lemonadeChange(vector<int>& bills) {\n        int state = 0;\n        \n        for (int bill : bills) {\n            if (bill == 5) {\n                state++;\n            } else if (bill == 10) {\n                if (!(state & 0xFFFF)) return false;\n                state--;\n                state += 0x10000;\n            } else { // bill == 20\n                if ((state & 0xFFFF0000) && (state & 0xFFFF)) {\n                    state -= 0x10001;\n                } else if ((state & 0xFFFF) >= 3) {\n                    state -= 3;\n                } else {\n                    return false;\n                }\n            }\n        }\n        \n        return true;\n    }\n};\n\n```\n```Python []\nclass Solution:\n    def lemonadeChange(self, bills: List[int]) -> bool:\n        state = 0  \n        \n        for bill in bills:\n            if bill == 5:\n                state += 1  \n            elif bill == 10:\n                if not (state & 0xFFFF):  \n                    return False\n                state -= 1  \n                state += 0x10000  \n            else:  \n                if (state & 0xFFFF0000) and (state & 0xFFFF): \n                    state -= 0x10001  \n                elif (state & 0xFFFF) >= 3:  $5\n                    state -= 3\n                else:\n                    return False\n        \n        return True\n\n```\n```Go []\nfunc lemonadeChange(bills []int) bool {\n    state := 0\n    \n    for _, bill := range bills {\n        if bill == 5 {\n            state++\n        } else if bill == 10 {\n            if state & 0xFFFF == 0 {\n                return false\n            }\n            state--\n            state += 0x10000\n        } else { // bill == 20\n            if state & 0xFFFF0000 != 0 && state & 0xFFFF != 0 {\n                state -= 0x10001\n            } else if state & 0xFFFF >= 3 {\n                state -= 3\n            } else {\n                return false\n            }\n        }\n    }\n    \n    return true\n}\n\n```\n```JavaScript []\n/**\n * @param {number[]} bills\n * @return {boolean}\n */\nvar lemonadeChange = function(bills) {\n    let state = 0;\n    \n    for (let bill of bills) {\n        if (bill === 5) {\n            state++;\n        } else if (bill === 10) {\n            if (!(state & 0xFFFF)) return false;\n            state--;\n            state += 0x10000;\n        } else { // bill === 20\n            if ((state & 0xFFFF0000) && (state & 0xFFFF)) {\n                state -= 0x10001;\n            } else if ((state & 0xFFFF) >= 3) {\n                state -= 3;\n            } else {\n                return false;\n            }\n        }\n    }\n    \n    return true;\n};\n```\n---\n
['Array', 'Stack', 'Greedy', 'Bit Manipulation', 'C++', 'Java', 'Go', 'Python3', 'Rust', 'JavaScript']