Twitter OA Activate Fountain
(This question has been seen in the interviews of the following companies: Twitter)
Activate Fountain
There is a one-dimensional garden of length n. In each position of the n length garden, a fountain has been installed. The fountain at the ith position has a value a[i] (where 1 <= i <= n) that describes the coverage limit of fountain i. A fountain can cover the range from the position max( (i - a[i]), 1) to min ((i + a[i]), n).
For example, if garden length n = 3 and a = {1, 2, 1}, then:
For position 1: a[1] = 1, range = 1 to 2.
For position 2: a[2] = 2, range = 1 to 3.
For position 3: a[3] = 1, range = 2 to 3.
In the beginning, all the fountains are switched off. Determine the minimum number of fountains you need to activate so that whole n length garden will be covered by water. In the example, the 1 fountain at position a[2] covers the whole garden.
Function Description
Complete the function fountainActivation in the editor below. The function must return an integer that denotes the minimum number of fountains that must be activated to cover the entire garden by water.
fountainActivation has the following parameter:
a[a[O)... a[n-1]]: an array of integers
Constraints
• 1 <= n <= 10^5
• 0 <= a[i] <= min( n, 100) (where 1 <= i <= 10^5)
Sample Input
3,1,1,1
Sample Output
1
Explanation
Here, a = {1, 1, 1)
If the 2nd fountain is active, the range from position 1 to 3 will be covered. The total number of fountains needed is 1.
Copyright © A++ Code Bootcamp 2023