A coastal authority operates a fleet of beacons, each broadcasting at a fixed signal range measured in nautical miles. Before the fleet can be certified for the season, every beacon still in service must broadcast at or above a required minimum range.
Certification works in passes: on each pass, the authority decommissions whichever beacon still in service currently has the smallest range (if several beacons are tied for smallest, decommissioning any one of them counts as a single pass). This repeats until every beacon still in service broadcasts at or above the required floor. Report how many passes this takes.
The first line contains two integers n and k — the number of beacons in the fleet and the required minimum range.
The second line contains n integers, the current broadcast range of each beacon, in fleet order.
Print a single integer: the minimum number of decommissioning passes needed so that every beacon still in service has a range of at least k.
Example 1
Input
5 10 2 11 10 1 3
Expected
3
Explanation
The floor is 10. Beacons with ranges 2, 1, and 3 are each below it and get decommissioned one pass at a time (the current weakest each time); after three passes only ranges 11 and 10 remain, both at or above 10, so the answer is 3.
Example 2
Input
5 1 1 1 2 4 9
Expected
0
Explanation
The required floor is 1, and every beacon already broadcasts at or above 1, so zero decommissioning passes are needed.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →