Dada una array arr[] de N enteros donde el i -ésimo elemento representa la cantidad de agua requerida por la planta en el i -ésimo índice y un entero K , la tarea es calcular el número de operaciones requeridas para regar todas las plantas usando un recipiente que puede contener como máximo K litros de agua en donde cada operación,
- Puede moverse a la planta adyacente a la izquierda oa la derecha.
- Además, hay un río en el índice -1 desde donde se puede rellenar el contenedor tantas veces como se desee.
- Tenga en cuenta que inicialmente, en el índice -1 y cualquier planta no se puede regar parcialmente durante ningún paso.
Ejemplos:
Entrada: arr[] = {2, 2, 3, 3}, K = 5
Salida: 14
Explicación: Para el ejemplo anterior, durante las primeras 2 operaciones: las plantas en el índice 0 y 1 se pueden regar.
Como no tenemos suficiente agua para la 3ra planta, regresar al río en 2 operaciones.
Rellenar el contenedor y volver a la 3ª planta en 3 operaciones.
Del mismo modo, no tenemos suficiente agua para la cuarta planta.
Así que rellene el contenedor y regrese a la 4ª planta en un total de 7 operaciones.
Por lo tanto, se requieren un total de 14 operaciones.Entrada: arr[] = {1, 2, 3, 4}, K = 3
Salida: -1
Explicación: No es posible regar completamente la cuarta planta usando un recipiente de capacidad 3.
Enfoque: El problema dado es un problema basado en la implementación. Se puede resolver siguiendo los siguientes pasos:
- Cree una variable current_capacity para almacenar la cantidad actual de agua en el contenedor. Inicialmente, current_capacity = K .
- Recorra la array dada arr[] usando una variable i y realice las siguientes operaciones:
- Si arr[i] > K , devuelve -1 .
- Si arr[i] > current_capacity , agregue 2*i + 1 al recuento de operaciones y establezca current_capacity = K – arr[i] .
- De lo contrario, agregue 1 al recuento de operaciones y establezca current_capacity = current_capacity – arr[i] .
A continuación se muestra la implementación del enfoque anterior:
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 plants
int 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 Code
int main()
{
vector<int> arr{ 2, 2, 3, 3 };
int K = 5;
cout << reqOperationCnt(arr, K);
return 0;
}
Java
// Java program for the above approach
import 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 approach
using 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 plants def 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 Code arr = [2, 2, 3, 3] K = 5 print(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>
14
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por manikajoshi500 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA