lemonade change

sherxon · Aug 16, 2018 · 29ea919 · 29ea919
1 parent 5eba62a
commit 29ea919
Show file tree

Hide file tree

Showing 2 changed files with 80 additions and 0 deletions.
diff --git a/src/problems/Easy.txt b/src/problems/Easy.txt
@@ -1350,3 +1350,49 @@ Since the list has two middle nodes with values 3 and 4, we return the second on
 Note:
 
 The number of nodes in the given list will be between 1 and 100.
+
+123)Lemonade Change
+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 don't have any change in hand at first.
+
+Return true if and only if you can provide every customer with correct change.
+
+
+
+Example 1:
+
+Input: [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: [5,5,10]
+Output: true
+Example 3:
+
+Input: [10,10]
+Output: false
+Example 4:
+
+Input: [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't give change of $15 back because we only have two $10 bills.
+Since not every customer received correct change, the answer is false.
+
+
+Note:
+
+0 <= bills.length <= 10000
+bills[i] will be either 5, 10, or 20.
diff --git a/src/problems/easy/LemonadeChange.java b/src/problems/easy/LemonadeChange.java
@@ -0,0 +1,34 @@
+package problems.easy;
+
+/**
+ * Why Did you create this class? what does it do?
+ */
+public class LemonadeChange {
+    public boolean lemonadeChange(int[] bills) {
+        int[] a = new int[3];
+        for (int i = 0; i < bills.length; i++) {
+            if (bills[i] == 5) {
+                a[0]++;
+                continue;
+            } else if (bills[i] == 10) {
+                a[1]++;
+                a[0]--;
+                if (a[0] < 0)
+                    return false;
+            } else {
+                a[2]++;
+                if (a[0] < 1)
+                    return false;
+                a[0]--;
+                if (a[1] > 0) {
+                    a[1]--;
+                } else {
+                    a[0] -= 2;
+                    if (a[0] < 0)
+                        return false;
+                }
+            }
+        }
+        return true;
+    }
+}