Last Updated: 6 Sep, 2021
Watering Flowers
Easy
Asked in companies
Takahashi has a garden with ‘n’ beautiful flowers in a row. He waters exactly “arr[i]” liters of water to ith flowers from left to right daily to keep them beautiful. He has a container that can contain ‘k’ liters of water. But he follows certain rules to water all the plants:
Water a plant if he has sufficient water in the container, otherwise refill it.
You can only refill at the water tank which is placed one step before the first flower.
Takahashi wants to know the minimum number of steps he needs to water all the flowers.
For Example :
Let arr = {3, 5, 1, 2}, k = 6
Now in this example, he will first move to the first flower and water it. Now his container contains only 3 liters of water, hence he will refill the container, so he goes 1 step back and refills, comes to the 2nd flower, after watering the second flower, he still has 1 liter of water and 1 flower left. So he will water that flower and return to refill. Now he will come to the last flower and water it.
Hence the total steps taken are: 1 + 1 + 2 + 1 + 3 + 4 = 12.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.
The first line of each test case contains two integers ‘n’ and ‘k’, denoting the number of flowers and capacity of the container, respectively.
The second line of the test case contains an array “arr” of size ‘n’, where “arr[i]” denotes the amount of water needed to the ith flower.
Output Format :
For each test case, print a single integer “answer” denoting the total steps taken by Takahashi.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
Constraints :
1 <= T <= 100
1 <= N <= 10^4
1 <= k <= 10^5
1 <= arr[i] <= k
Time limit: 1 sec
Approaches
In this approach, we will check for every flower if we can water it or not, if we can water it we will water that flower and check for the next flower, else we will go and refill our container.
The steps are as follows:
- Take two integers, “steps” and “cap” in which we will store the total step count and the remaining capacity of the water can, respectively.
- Initialize “cap” with ‘k’ as initially, we have ‘k’ liters of water in the container.
- Iterate through the loop from 0 to n-1(say iterator be i):
- Check if the current value of “arr[i]” <= “cap”:
- If the value of “arr[i]” is less than “cap” then update “cap” -= “arr[i]”.
- Else update “step” += 2 * ‘i’ as we have to go and refill our container and update “cap” = ‘k’ - “arr[i]”.
- Increment “step” count by 1.
- Check if the current value of “arr[i]” <= “cap”:
- Return “step”.
Similar problems