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.

Constraints:

  • 1 <= bills.length <= 105
  • bills[i] is either 5, 10, or 20.

Note: This problem is from LeetCode.
βœ… Compiled
βœ… Executed
βœ… Correct
program main
    implicit none

    integer, parameter :: n = 5
    integer, dimension(n) :: bills
    logical :: result

    bills = [5, 5, 5, 10, 20]
    result = lemonade(bills)
    write (*, '(L1)') result

    bills = [5, 5, 10, 10, 20]
    result = lemonade(bills)
    write (*, '(L1)') result

contains

    function lemonade(bills) result(result)
        implicit none
        integer, intent(in) :: bills(:)
        logical :: result

        integer :: i, j, k, l, m, n, o
        integer :: total

        result = .true.

        ! Initialize variables
        total = 0
        i = 1
        j = 1
        k = 1
        l = 1
        m = 1
        n = 1
        o = 1

        ! Loop through the bills
        do while (i <= ubound(bills, 1))
            select case (bills(i))
                case (5)
                    total = total + 5
                    i = i + 1
                case (10)
                    if (total >= 5) then
                        total = total - 5
                        i = i + 1
                    else
                        result = .false.
                        exit
                    end if
                case (20)
                    if (total >= 10) then
                        total = total - 10
                        i = i + 1
                    else
                        result = .false.
                        exit
                    end if
            end select
        end do

        ! Check if there is enough money for the change
        if (total /= 0) then
            result = .false.
        end if

    end function lemonade
end program main
❌ Compiled
❌ Executed
❌ Correct
module lemonade_stand
implicit none
contains

function solve(bills) result(success)
integer, intent(in) :: bills(:)
logical :: success
integer :: i, bill, change

! Initialize variables
success = .true.
i = 1
bill = 0
change = 0

! Process each bill
do while (i <= size(bills))
    ! Check if the bill is valid
    if (bills(i) /= 5 .and. bills(i) /= 10 .and. bills(i) /= 20) then
        success = .false.
        exit
    end if

    ! Update the bill and change
    bill = bills(i)
    change = bill - 5

    ! Check if we have enough change
    if (change < 0) then
        success = .false.
        exit
    end if

    ! Update the change
    change = change - 5

    ! Increment the index
    i = i + 1
end do

end function solve
end module

program test
use lemonade_stand
implicit none

! Test case 1:
print *, solve([5, 5, 5, 10, 20])

! Test case 2:
print *, solve([5, 5, 10, 10, 20])

! Test case 3:
print *, solve([5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
🌐 Data from online sources
class MyCircularQueue:

    def __init__(self, k: int):
        self.data = [0] * k
        self.head = 0
        self.tail = -1
        self.size = 0
        self.capacity = k

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.tail = (self.tail + 1) % self.capacity
        self.data[self.tail] = value
        self.size += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.head = (self.head + 1) % self.capacity
        self.size -= 1
        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.data[self.head]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.data[self.tail]

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == self.capacity

The circular queue is implemented using an array with fixed capacity. The operations are performed based on FIFO principle, and the last position is connected back to the first position to make a circle. We keep a head and tail pointer, as well as the current size of the queue. Whenever an element is enqueued, we move the tail pointer forward (circulating back to the start of the array when necessary) and increase the size. When an element is dequeued, we move the head pointer forward and decrease the size. We can check if the queue is empty by comparing the size to 0 and check if the queue is full by comparing the size to the capacity. All operations have O(1) time complexity.

🌐 Data from online sources
class MyCircularQueue {
public:
    MyCircularQueue(int k) {
        data.resize(k);
        head = 0;
        tail = -1;
        size = 0;
        capacity = k;
    }

    bool enQueue(int value) {
        if (isFull()) {
            return false;
        }
        tail = (tail + 1) % capacity;
        data[tail] = value;
        size++;
        return true;
    }

    bool deQueue() {
        if (isEmpty()) {
            return false;
        }
        head = (head + 1) % capacity;
        size--;
        return true;
    }

    int Front() {
        if (isEmpty()) {
            return -1;
        }
        return data[head];
    }

    int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return data[tail];
    }

    bool isEmpty() {
        return size == 0;
    }

    bool isFull() {
        return size == capacity;
    }

private:
    vector<int> data;
    int head, tail, size, capacity;
};

The circular queue is implemented using an array with fixed capacity. The operations are performed based on FIFO principle, and the last position is connected back to the first position to make a circle. We keep a head and tail pointer, as well as the current size of the queue. Whenever an element is enqueued, we move the tail pointer forward (circulating back to the start of the array when necessary) and increase the size. When an element is dequeued, we move the head pointer forward and decrease the size. We can check if the queue is empty by comparing the size to 0 and check if the queue is full by comparing the size to the capacity. All operations have O(1) time complexity.