Bus Ticket Change

JavaView on GFG

Time: O(n)

Space: O(1)

Problem Overview

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

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?