Bus Ticket Change

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Check if conductor can give change for all passengers given ticket prices and available coins.

Algorithm

1Simulate: for each passenger fare, check if exact change can be made from current coins. Update coin counts.

Common Pitfalls

•Greedy: always use largest denomination first when giving change. Track available coin counts.

Bus Ticket Change.java

Java

// Approach: Greedy / simulation. Process purchases and track available change denominations.
// Time: O(n) Space: O(1)
class Solution {
    public boolean canServe(int[] arr) {
        if (arr[0] != 5)
            return false;
        int num[] = new int[21];
        for (int i = 0; i < arr.length; i++) {
            num[arr[i]]++;
            if (arr[i] == 10) {
                if (num[5] > 0)
                    num[5]--;
                else
                    return false;
            } else if (arr[i] == 20) {
                if (num[5] > 0 && num[10] > 0) {
                    num[5]--;
                    num[10]--;
                } else if (num[5] > 2)
                    num[5] = num[5] - 3;
                else
                    return false;
            }
        }
        return true;
    }
}

Was this solution helpful?