# Minimum Number Of Taps To Water Garden

Posted: 12 Nov, 2020

Difficulty: Hard

#### The gardener wants to water the garden by opening the minimum number of taps. The garden is one-dimensional along the x-axis of length N i.e. the garden starts from point 0 and ends at point N. There are N + 1 tap located at points [0, 1, 2, …, N] in the garden.

#### You are given an integer N, and an array named “ranges” of size N + 1(0-indexed). The ith tap, if opened, can water the gardener from point (i - ranges[i]) to (i + ranges[i]) including both. The task is to find the minimum number of taps that should be open to water the whole garden, return -1 if the garden can not be watered.

##### Example :

##### Follow Up:

```
Can you solve the problem in O(N) time?
```

##### Input Format:

```
The first line contains a single integer T representing the number of test cases.
The first line of each test case will contain the integer N.
The second and the last line of each test case will contain N single space-separated integers representing the elements of the array “ranges”.
```

##### Output format :

```
For each test case, print a single integer representing the value of the minimum number of taps needed to open by the gardener to fill the whole garden.
```

##### Note:

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

##### Constraints:

```
1 <= T <= 10
1 <= N <= 10^4
0 <= ranges[i] <= 100
Time Limit: 1 sec
```