A stretch of coastline is divided into n plots arranged in a single row and numbered from left to right. Each plot already either holds a watch-beacon (marked 1) or is empty (marked 0), and it is guaranteed that no two existing beacons occupy adjacent plots. The Coastal Guard wants to install k additional beacons in currently empty plots. Because two beacons in neighboring plots interfere with each other's signal, after installation no plot holding a beacon may be immediately next to another plot that also holds a beacon (old or new). Determine whether all k new beacons can be installed somewhere while keeping this no-adjacent-beacons rule satisfied for the whole row.
n and k — the number of plots and the number of beacons to install.n space-separated integers, each 0 or 1, describing the current state of the plots from left to right.Print true if it is possible to install all k beacons while respecting the no-adjacent-beacons rule, and false otherwise.
0 or 1.1s in the given row are adjacent.Example 1
Input
5 1 1 0 0 0 1
Expected
true
Explanation
The row is [1,0,0,0,1]. The middle plot (index 2) is empty and both of its neighbors (indices 1 and 3) are empty, so a beacon can be placed there without touching either existing beacon. That satisfies the 1 requested beacon, so the answer is true.
Example 2
Input
6 2 1 0 0 0 1 0
Expected
false
Explanation
Existing beacons sit at indices 0 and 4. Of the empty plots (1, 2, 3, 5), index 1 is adjacent to the beacon at 0, and indices 3 and 5 are each adjacent to the beacon at 4, so only index 2 can safely take a new beacon. At most 1 new beacon can be placed, which is fewer than the 2 requested, so the answer is false.
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 →