**Question 4 **

Street Lights are installed at every position along a 1-D road of length n.

Locations[] (an array) represents the coverage limit of these lights. The ith light has a coverage limit of locations[i] that can range from the position max((i – locations[i]), 1) to min((i + locations[i]), n ) (Closed intervals). Initially all the lights are switched off. Find the minimum number of fountains that must be switched on to cover the road.

Example

n = 3

locations[] = {0, 2, 13}then

For position 1: locations[1] = 0, max((1 – 0),

1) to mini (1+0), 3) gives range = 1 to 1

For position 2: locations[2] = 2, max((2-2),

1) to min( (2+2), 3) gives range = 1 to 3

For position 3: locations[3] = 1, max( (3-1),

1) to min( (3+1), 3) gives range = 2 to 3

For the entire length of this road to be covered, only the light at position 2 needs to be activated.

Function Description

Returns

int: the minimum number of street lights that must be activated

Constraints

- 1<_n<_ 10^5
- O<_locations[i] <_ mini (n,100) (where 1 <_1<_

10^5)

► Input Format For Custom Testing

Sample Case 0

Sample Input For Custom Testing

3 ->locations[] size n = 3

1 ->locations[] [1, 1, 1]

1 ->Sample Output

Sample Output

1

Login/Signup to comment