Given an array arr[] of N integers where ith element represents the amount of water required by the plant at ith index and an integer K, the task is to calculate the count of operations required to water all the plants using a container that can hold at most K liters of water wherein each operation,
- You can move to the adjacent plant to the left or to the right.
- Also, there is a river at index -1 from where the container can be refilled any number of times.
- Note that initially, at index -1 and any plant can not be watered partially during any step.
Examples:
Input: arr[] = {2, 2, 3, 3}, K = 5
Output: 14
Explanation: For the above example, during the first 2 operations: the plants at index 0 and 1 can be watered.Â
Since we do not have enough water for the 3rd plant, return to the river in 2 operations.
Refill the container and return to the 3rd plant in 3 operations.Â
Similarly, we do not have enough water for the 4th plant.Â
So refill the container and come back to the 4th plant in a total of 7 operations.Â
Therefore, a total of 14 operations are required.Input: arr[] = {1, 2, 3, 4}, K = 3
Output: -1
Explanation: It is not possible to fully water the 4th plant using a container of capacity 3.
Â
Approach: The given problem is an implementation-based problem. It can be solved using the following steps:
- Create a variable current_capacity to store the current quantity of water in the container. Initially, current_capacity = K.
- Traverse the given array arr[] using a variable i and perform the following operations:
- If arr[i] > K, return -1.
- If arr[i] > current_capacity, add 2*i + 1 into the operation count and set current_capacity = K – arr[i].
- Otherwise, add 1 to the operation count and set current_capacity = current_capacity – arr[i].
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;Â
// Function to find count of operation// required to water all the plantsint reqOperationCnt(vector<int>& arr, int K){Â
    // Stores current capacity    // of the container    int current_capacity = K;Â
    // Stores the final count    int cnt = 0;Â
    // Loop to traverse arr[]    for (int i = 0; i < arr.size(); i++) {Â
        // If required water is        // more than max capacity        if (arr[i] > K) {            return -1;        }Â
        // If container does not        // have enough water        if (current_capacity < arr[i]) {Â
            // Update cnt            cnt += 2 * i + 1;Â
            // Update current capacity            // to the remaining water            current_capacity = K - arr[i];        }        else {Â
            // Update current capacity            cnt++;            current_capacity -= arr[i];        }    }Â
    // Return Answer    return cnt;}Â
// Driver Codeint main(){Â
    vector<int> arr{ 2, 2, 3, 3 };    int K = 5;    cout << reqOperationCnt(arr, K);Â
    return 0;} |
Java
// Java program for the above approachimport java.util.*;public class GFG {Â
  // Function to find count of operation  // required to water all the plants  static int reqOperationCnt(int []arr, int K)  {Â
    // Stores current capacity    // of the container    int current_capacity = K;Â
    // Stores the final count    int cnt = 0;Â
    // Loop to traverse arr[]    for (int i = 0; i < arr.length; i++) {Â
      // If required water is      // more than max capacity      if (arr[i] > K) {        return -1;      }Â
      // If container does not      // have enough water      if (current_capacity < arr[i]) {Â
        // Update cnt        cnt += 2 * i + 1;Â
        // Update current capacity        // to the remaining water        current_capacity = K - arr[i];      }      else {Â
        // Update current capacity        cnt++;        current_capacity -= arr[i];      }    }Â
    // Return Answer    return cnt;  }Â
  // Driver code  public static void main (String args[]) {    int []arr = { 2, 2, 3, 3 };    int K = 5;    System.out.println(reqOperationCnt(arr, K));  }}Â
// This code is contributed by Samim Hossain Mondal. |
C#
// C# program for the above approachusing System;class GFG {Â
  // Function to find count of operation  // required to water all the plants  static int reqOperationCnt(int []arr, int K)  {Â
    // Stores current capacity    // of the container    int current_capacity = K;Â
    // Stores the final count    int cnt = 0;Â
    // Loop to traverse arr[]    for (int i = 0; i < arr.Length; i++) {Â
      // If required water is      // more than max capacity      if (arr[i] > K) {        return -1;      }Â
      // If container does not      // have enough water      if (current_capacity < arr[i]) {Â
        // Update cnt        cnt += 2 * i + 1;Â
        // Update current capacity        // to the remaining water        current_capacity = K - arr[i];      }      else {Â
        // Update current capacity        cnt++;        current_capacity -= arr[i];      }    }Â
    // Return Answer    return cnt;  }Â
  // Driver code  public static void Main () {    int []arr = { 2, 2, 3, 3 };    int K = 5;    Console.Write(reqOperationCnt(arr, K));  }}Â
// This code is contributed by Samim Hossain Mondal. |
Python3
# Python code for the above approachÂ
# Function to find count of operation# required to water all the plantsdef reqOperationCnt(arr, K):Â
    # Stores current capacity    # of the container    current_capacity = KÂ
    # Stores the final count    cnt = 0Â
    # Loop to traverse arr[]    for i in range(len(arr)):Â
        # If required water is        # more than max capacity        if (arr[i] > K):            return -1Â
        # If container does not        # have enough water        if (current_capacity < arr[i]):Â
            # Update cnt            cnt += 2 * i + 1Â
            # Update current capacity            # to the remaining water            current_capacity = K - arr[i]Â
        else:Â
            # Update current capacity            cnt += 1            current_capacity -= arr[i]Â
    # Return Answer    return cntÂ
# Driver Codearr = [2, 2, 3, 3]K = 5print(reqOperationCnt(arr, K))Â
# This code is contributed by Saurabh Jaiswal |
Javascript
<script>Â Â Â Â Â Â // JavaScript code for the above approach Â
      // Function to find count of operation      // required to water all the plants      function reqOperationCnt(arr, K) {Â
          // Stores current capacity          // of the container          let current_capacity = K;Â
          // Stores the final count          let cnt = 0;Â
          // Loop to traverse arr[]          for (let i = 0; i < arr.length; i++) {Â
              // If required water is              // more than max capacity              if (arr[i] > K) {                  return -1;              }Â
              // If container does not              // have enough water              if (current_capacity < arr[i]) {Â
                  // Update cnt                  cnt += 2 * i + 1;Â
                  // Update current capacity                  // to the remaining water                  current_capacity = K - arr[i];              }              else {Â
                  // Update current capacity                  cnt++;                  current_capacity -= arr[i];              }          }Â
          // Return Answer          return cnt;      }Â
      // Driver Code      let arr = [2, 2, 3, 3];      let K = 5;      document.write(reqOperationCnt(arr, K));Â
     // This code is contributed by Potta Lokesh  </script> |
Output
14
Time Complexity: O(N) since one traversal of the array is required to complete all operations hence the overall time required by the algorithm is linear
Auxiliary Space: O(1) since no extra array is used so the space taken by the algorithm is constant
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] There you will find 65022 additional Info on that Topic: geeksforgeeks.org/count-of-operation-required-to-water-all-the-plants/ […]
… [Trackback]
[…] Read More Info here to that Topic: geeksforgeeks.org/count-of-operation-required-to-water-all-the-plants/ […]