Walmart OA

不会做

Min number of fountains needed to water the array :

There is a linear garden from 1 to n. At each point there is a fountain. Given array a[n]tells info about fountain such that its range is max(i-a[i],1) to the left of fountain to min(i+a[i],n) to the right of fountain. Find minimum no. of fountains needed to be activated so that whole garden is covered.

Example: If n=3 and a={1,2,1} then second fountain has range 1 to 3. So only 1 fountain needed. Here fountain at 1 has range of 1 to 2, fountain at 2 has range of 1 to 3 and fountain at 3 has range of 2 to 3 So only fountain 2 is enough to be activated to cover the whole garden.