Lemonade Change
Published: 2022-10-30 05:40:03

At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time (in the order specified by bills). Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill. You must provide the correct change to each customer so that the net transaction is that the customer pays $5.

Note that you do not have any change in hand at first.

Given an integer array bills where bills[i] is the bill the ith customer pays, return true if you can provide every customer with the correct change, or false otherwise.

 

Example 1:

Input: bills = [5,5,5,10,20]
Output: true
Explanation: 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

Example 2:
Input: bills = [5,5,10,10,20]
Output: false
Explanation: 
From the first two customers in order, we collect two $5 bills.
For the next two customers in order, we collect a $10 bill and give back a $5 bill.
For the last customer, we can not give the change of $15 back because we only have two $10 bills.
Since not every customer received the correct change, the answer is false.

solution 1
```js
/**
 * @param {number[]} bills
 * @return {boolean}
 */
var lemonadeChange = function(bills) {
    let change={'5':0, '10':0};
    for (let bill of bills) {
        if (bill==5) change[5]++;
        else if (bill==10) {
            if (!change[5]) return false
            change[10]++;
            change[5]--;
        } else { //bill==20
            if (change[5] && change[10]) {  
			// first way for giving change: bill of 10 + bill of 5
                change[10]--;
                change[5]--;
            }else if(change[5]>=3) {
			// second way for giving change: 3 bills of 5
                change[5] -= 3 ;
            }else return false
        }
    }
    return true
}
```

Solution 2: elongated but works same as above

```js
/**
 * @param {number[]} bills
 * @return {boolean}
 */
var lemonadeChange = function (bills) {
  let walletBalance = {
    20: 0,
    10: 0,
    5: 0,
  };

  for (let i = 0; i < bills.length; i++) {
    let bill = bills[i];
    let change = bill - 5;
    if (change !== 0) {
      let twentyCount = 0;
      let tenCount = 0;
      let fiveCount = 0;

      if (walletBalance[20]) {
        twentyCount = Math.floor(change / 20);
        if (twentyCount) {
          change = change - twentyCount * 20;
        }
      }

      if (walletBalance[10]) {
        tenCount = Math.floor(change / 10);
        if (tenCount) {
          change = change - tenCount * 10;
        }
      }

      if (walletBalance[5]) {
        fiveCount = Math.floor(change / 5);
        if (fiveCount) {
          change = change - fiveCount * 5;
        }
      }

      if (
        walletBalance[20] >= twentyCount &&
        walletBalance[10] >= tenCount &&
        walletBalance[5] >= fiveCount &&
        change === 0
      ) {
        walletBalance[20] = walletBalance[20] - twentyCount;
        walletBalance[10] = walletBalance[10] - tenCount;
        walletBalance[5] = walletBalance[5] - fiveCount;
        walletBalance[bill]++;
      } else {
        return false;
      }
    } else {
      walletBalance[bill]++;
    }
  }
  return true;
};

console.log(lemonadeChange([5, 5, 5, 10, 20]));
console.log(lemonadeChange([5, 5, 10, 10, 20]));

```