FASTag Booth Change
A toll booth charges a flat ₹50 per vehicle and starts with no cash. Vehicles arrive in order, each paying with a single ₹50, ₹100, or ₹200 note. Decide whether you can give correct change to every vehicle from notes received earlier.
Problem
Each toll is ₹50. Given an array bills of the notes vehicles pay with (each 50, 100, or 200), in arrival order, return true if you can provide correct change to every vehicle. You start with no notes and may only use notes collected from earlier vehicles.
Input
An array bills of n values, each in {50, 100, 200} (1 ≤ n ≤ 10^5).
Output
A boolean — true if every vehicle gets correct change.
Constraints
- Toll is exactly ₹50 per vehicle
- Change must come only from previously received notes
- A ₹200 payment needs ₹150 change: a ₹100+₹50 or three ₹50s
Examples
Example 1
Input
bills = [50,50,100,50,200]
Output
true
Collect two ₹50s, give one back for the ₹100, and use ₹100+₹50 to change the ₹200.
Example 2
Input
bills = [50,200]
Output
false
The ₹200 needs ₹150 change but only one ₹50 is on hand.