# Minimum Initial Energy Required To Cross Street

Given an array containing positive and negative numbers. The array represents checkpoints from one end to other end of street. Positive and negative values represent amount of energy at that checkpoint. Positive numbers increase the energy and negative numbers decrease. Find the minimum initial energy required to cross the street such that Energy level never becomes 0 or less than 0.

** Note :** The value of minimum initial energy required will be 1 even if we cross street successfully without loosing energy to less than and equal to 0 at any checkpoint. The 1 is required for initial check point.

Become a success story instead of just reading about them. Prepare for coding interviews at Amazon and other top product-based companies with our **Amazon Test Series**. Includes **topic-wise practice questions on all important DSA topics** along with **10 practice contests** of 2 hours each. Designed by industry experts that will surely help you practice and sharpen your programming skills. Wait no more, start your preparation today!

**Examples :**

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 least7because having7as 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

We take initial minimum energy 0 i.e; initMinEnergy = 0 and energy at any checkpoint as currEnergy = 0. Now traverse each checkpoint linearly and add energy level at each i’th checkpoint i.e; currEnergy = currEnergy + arr[i]. If currEnergy becomes non-positive, then we need at least “abs(currEnergy) + 1” extra initial energy to cross this point. Therefore we update initMinEnergy = (initMinEnergy + abs(currEnergy) + 1). We also update currEnergy = 1 as we now have the required extra minimum initial energy for next point.

Below is the implementation of above idea.

## 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.` |

## Python

`# Python program to find minimum initial enery to` `# reach end` `# Function to calculate minimum initial enery` `# arr[] stores enery 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>` |

**Output :**

7

**Time Complexity :** O(n) **Auxiliary Space :** O(1)

This article is contributed by **Shashank Mishra ( Gullu )**. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.