Along a long border wall stand n numbered watchtowers, numbered 0 to n-1 from one end of the wall to the other. On a given night, each tower either lights a signal beacon or stays dark; this is recorded as a sequence of n values, one per tower, where 1 means the tower's beacon is lit that night and 0 means it stays dark. To keep two beacons' smoke plumes from drifting into each other, wall regulations require that between any two lit towers there be at least k dark towers separating them — equivalently, if two lit towers sit at indices a and b with a < b, then b - a must be at least k + 1.
Given the night's sequence and the required minimum k, determine whether every pair of lit towers that night satisfies the spacing rule.
The first line contains two integers n and k. The second line contains n integers, each either 0 or 1, describing the state of each tower in order.
Print a single line containing exactly true if every two lit towers are at least k towers apart (in the sense above), or false otherwise.
Example 1
Input
10 2 0 1 0 0 0 1 0 0 1 0
Expected
true
Explanation
Lit towers are at indices 1, 5, and 8. Consecutive gaps are 5-1=4 and 8-5=3, and both are at least k+1=3, so every pair satisfies the spacing rule: true.
Example 2
Input
6 2 1 0 0 1 0 1
Expected
false
Explanation
Lit towers are at indices 0, 3, and 5. The gap between index 3 and index 5 is 2, which is less than k+1=3, so the rule is violated: 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 →