Dada una array que contiene números positivos y negativos. La array representa los puntos de control de un extremo al otro de la calle. Los valores positivos y negativos representan la cantidad de energía en ese punto de control. Los números positivos aumentan la energía y los números negativos disminuyen. Encuentre la energía inicial mínima requerida para cruzar la calle de modo que el nivel de energía nunca llegue a 0 o sea inferior a 0.
Nota: El valor de la energía inicial mínima requerida será 1 incluso si cruzamos la calle con éxito sin perder energía a menos de 0 en ningún punto de control. El 1 es necesario para el punto de control inicial.
Ejemplos:
Input : arr[] = {4, -10, 4, 4, 4} Output: 7 Suppose initially we have energy = 0, now at 1st checkpoint, we get 4. At 2nd checkpoint, energy gets reduced by -10 so we have 4 + (-10) = -6 but at any checkpoint value of energy can not less than equals to 0. So initial energy must be at least 7 because having 7 as initial energy value at 1st checkpoint our energy will be = 7+4 = 11 and then we can cross 2nd checkpoint successfully. Now after 2nd checkpoint, all checkpoint have positive value so we can cross street successfully with 7 initial energy. Input : arr[] = {3, 5, 2, 6, 1} Output: 1 We need at least 1 initial energy to reach first checkpoint Input : arr[] = {-1, -5, -9} Output: 16
Tomamos la energía mínima inicial 0 es decir; initMinEnergy = 0 y energía en cualquier punto de control como currEnergy = 0. Ahora atraviese cada punto de control linealmente y agregue el nivel de energía en cada i-ésimo punto de control, es decir; energíaactual = energíaactual + arr[i]. Si currEnergy se vuelve no positivo, entonces necesitamos al menos «abs (currEnergy) + 1» energía inicial adicional para cruzar este punto. Por lo tanto, actualizamos initMinEnergy = (initMinEnergy + abs(currEnergy) + 1). También actualizamos currEnergy = 1 ya que ahora tenemos la energía inicial mínima adicional requerida para el siguiente punto.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find minimum initial energy to // reach end #include<bits/stdc++.h> using namespace std; // Function to calculate minimum initial energy // arr[] stores energy at each checkpoints on street int minInitialEnergy(int arr[], int n) { // initMinEnergy is variable to store minimum initial // energy required. int initMinEnergy = 0; // currEnergy is variable to store current value of // energy at i'th checkpoint on street int currEnergy = 0; // flag to check if we have successfully crossed the // street without any energy loss <= o at any checkpoint bool flag = 0; // Traverse each check point linearly for (int i=0; i<n; i++) { currEnergy += arr[i]; // If current energy, becomes negative or 0, increment // initial minimum energy by the negative value plus 1. // to keep current energy positive (at least 1). Also // update current energy and flag. if (currEnergy <= 0) { initMinEnergy += abs(currEnergy) +1; currEnergy = 1; flag = 1; } } // If energy never became negative or 0, then // return 1. Else return computed initMinEnergy return (flag == 0)? 1 : initMinEnergy; } // Driver Program to test the case int main() { int arr[] = {4, -10, 4, 4, 4}; int n = sizeof(arr)/sizeof(arr[0]); cout << minInitialEnergy(arr, n); return 0; }
Java
// Java program to find minimum // initial energy to reach end class GFG { // Function to calculate minimum // initial energy arr[] stores energy // at each checkpoints on street static int minInitialEnergy(int arr[], int n) { // initMinEnergy is variable to store // minimum initial energy required. int initMinEnergy = 0; // currEnergy is variable to store // current value of energy at // i'th checkpoint on street int currEnergy = 0; // flag to check if we have successfully // crossed the street without any energy // loss <= o at any checkpoint boolean flag = false; // Traverse each check point linearly for (int i = 0; i < n; i++) { currEnergy += arr[i]; // If current energy, becomes negative or 0, // increment initial minimum energy by the negative // value plus 1. to keep current energy // positive (at least 1). Also // update current energy and flag. if (currEnergy <= 0) { initMinEnergy += Math.abs(currEnergy) + 1; currEnergy = 1; flag = true; } } // If energy never became negative or 0, then // return 1. Else return computed initMinEnergy return (flag == false) ? 1 : initMinEnergy; } // Driver code public static void main(String[] args) { int arr[] = {4, -10, 4, 4, 4}; int n = arr.length; System.out.print(minInitialEnergy(arr, n)); } } // This code is contributed by Anant Agarwal.
Python3
# Python program to find minimum initial energy to # reach end # Function to calculate minimum initial energy # arr[] stores energy at each checkpoints on street def minInitialEnergy(arr): n = len(arr) # initMinEnergy is variable to store minimum initial # energy required initMinEnergy = 0; # currEnergy is variable to store current value of # energy at i'th checkpoint on street currEnergy = 0 # flag to check if we have successfully crossed the # street without any energy loss <= 0 at any checkpoint flag = 0 # Traverse each check point linearly for i in range(n): currEnergy += arr[i] # If current energy, becomes negative or 0, increment # initial minimum energy by the negative value plus 1. # to keep current energy positive (at least 1). Also # update current energy and flag. if currEnergy <= 0 : initMinEnergy += (abs(currEnergy) +1) currEnergy = 1 flag = 1 # If energy never became negative or 0, then # return 1. Else return computed initMinEnergy return 1 if flag == 0 else initMinEnergy # Driver program to test above function arr = [4, -10 , 4, 4, 4] print (minInitialEnergy(arr)) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
// C# program to find minimum // C# program to find minimum // initial energy to reach end using System; class GFG { // Function to calculate minimum // initial energy arr[] stores energy // at each checkpoints on street static int minInitialEnergy(int []arr, int n) { // initMinEnergy is variable to store // minimum initial energy required. int initMinEnergy = 0; // currEnergy is variable to store // current value of energy at // i'th checkpoint on street int currEnergy = 0; // flag to check if we have successfully // crossed the street without any energy // loss <= o at any checkpoint bool flag = false; // Traverse each check point linearly for (int i = 0; i < n; i++) { currEnergy += arr[i]; // If current energy, becomes negative or 0, // negativeincrement initial minimum energy // by the value plus 1. to keep current // energy positive (at least 1). Also // update current energy and flag. if (currEnergy <= 0) { initMinEnergy += Math.Abs(currEnergy) + 1; currEnergy = 1; flag = true; } } // If energy never became negative // or 0, then return 1. Else return // computed initMinEnergy return (flag == false) ? 1 : initMinEnergy; } // Driver code public static void Main() { int []arr = {4, -10, 4, 4, 4}; int n = arr.Length; Console.Write(minInitialEnergy(arr, n)); } } // This code is contributed by Nitin Mittal.
PHP
<?php // PHP program to find minimum // initial energy to reach end // Function to calculate minimum // initial energy arr[] stores // energy at each checkpoints on street function minInitialEnergy($arr, $n) { // initMinEnergy is variable // to store minimum initial // energy required. $initMinEnergy = 0; // currEnergy is variable to // store current value of energy // at i'th checkpoint on street $currEnergy = 0; // flag to check if we have // successfully crossed the // street without any energy // loss <= o at any checkpoint $flag = 0; // Traverse each check // point linearly for ($i = 0; $i < $n; $i++) { $currEnergy += $arr[$i]; // If current energy, becomes // negative or 0, increment // initial minimum energy by // the negative value plus 1. // to keep current energy // positive (at least 1). Also // update current energy and flag. if ($currEnergy <= 0) { $initMinEnergy += abs($currEnergy) + 1; $currEnergy = 1; $flag = 1; } } // If energy never became // negative or 0, then // return 1. Else return // computed initMinEnergy return ($flag == 0) ? 1 : $initMinEnergy; } // Driver Code $arr = array(4, -10, 4, 4, 4); $n = sizeof($arr); echo minInitialEnergy($arr, $n); // This code is contributed // by nitin mittal. ?>
Javascript
<script> // Javascript program to find minimum // initial energy to reach end // Function to calculate minimum // initial energy arr[] stores // energy at each checkpoints on street function minInitialEnergy(arr, n) { // initMinEnergy is variable // to store minimum initial // energy required. let initMinEnergy = 0; // currEnergy is variable to // store current value of energy // at i'th checkpoint on street let currEnergy = 0; // flag to check if we have // successfully crossed the // street without any energy // loss <= o at any checkpoint let flag = 0; // Traverse each check // point linearly for (let i = 0; i < n; i++) { currEnergy += arr[i]; // If current energy, becomes // negative or 0, increment // initial minimum energy by // the negative value plus 1. // to keep current energy // positive (at least 1). Also // update current energy and flag. if (currEnergy <= 0) { initMinEnergy += Math.abs(currEnergy) + 1; currEnergy = 1; flag = 1; } } // If energy never became // negative or 0, then // return 1. Else return // computed initMinEnergy return (flag == 0) ? 1 : initMinEnergy; } // Driver Code let arr = new Array(4, -10, 4, 4, 4); let n = arr.length; document.write(minInitialEnergy(arr, n)); // This code is contributed // by Saurabh Jaiswal </script>
7
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(1)
Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA