Watering Flowers

Easy
0/40
profile
Contributed by
38 upvotes
Asked in companies
WiseTech GlobalGoogle inc

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3 11
3 2 5
3 5
4 2 1
Sample Output 1 :
3
5
Explanation For Sample Output 1 :

In the first example, he will first move to the first flower and water it, after that he is left with 8 liters of water, now he will move to the second flower and water it, after watering it he is still left with 6 liters of water which is enough for the third flower, so he will move to the third flower. Hence the total steps taken is 3.


In the second example, he will first move one step to water the first flower, now he is left with only one liter of water, so he will return to the water tank i.e. 1 step behind, and then come to the second flower, water it and move to the third flower, hence the total steps taken are 5.
Sample Input 2 :
2
5 9
4 7 2 6 1
5 1
1 1 1 1 1
Sample Output 2 :
13
25
Hint

Iterate through the complete keyboard until we find the required character

Approaches (1)
Naive approach

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.
  • Return “step”.
Time Complexity

O( N ), where ‘N’ is the length of the array “arr”.

 

Since we are iterating through the whole array “arr”.

Hence, the total time complexity of this approach will be O( N ).

Space Complexity

O( 1 ).

 

We are not using any extra space.

Hence the space complexity will be O( 1 ).

Code Solution
(100% EXP penalty)
Watering Flowers
Full screen
Console