Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

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.

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

Detailed explanation

```
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”.
```

```
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.
```

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

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

```
2
3
0 0 0 0
7
1 2 1 0 2 1 0 1
```

```
-1
3
```

```
In test case 1, the ranges of taps are as follows : [ [ 0, 0 ], [ 1, 1 ], [ 2, 2 ] ]. So in the worst case, if we open all the taps, then it’s impossible to fill the gaps i.e (0-1), (1,2), (2,3). So it’s impossible to fill the garden.
In test case 2, the ranges of taps are as follows : [ [ -1, 1 ],[ -1, 3 ],[ 1, 3 ],[ 3, 3 ],[ 2, 6 ],[ 4, 6 ],[ 6, 6 ],[ 6, 8 ] ]. To fill the garden i.e [ 0, 7 ] , the gardener needs to open a minimum of three taps i.e. tap 2: [ -1, 3 ] , tap 5: [ 2, 6 ], tap 8: [ 6, 8 ] to fill the whole garden.
```

```
2
8
4 0 0 0 0 0 0 0 4
8
4 0 0 0 4 0 0 0 4
```

```
2
1
```