FastPrep

Description

Solutions

Minimum Start Value

🔥 FULLTIME📚RELATED PROBLEMS

Consider an array of integers and a non-zero positive starting value x. A running sum is calculated by adding each element of the array to x consecutively. Determine the minimum value of x such that the running sum is at least 1 after every iteration.

Function Description

Complete the function minStart in the editor.

minStart has the following parameter(s):

int arr[n]: an array of integers to sum

Returns

long: the minimum initial value

Example 1:

Input:  arr = [-5, 4, -2, 3, 1, -1, -6, -1, 0, 5]
Output: 8 
Explanation:
Any initial value less than 8 will fail. For example, the running sums for an initial value of 7 is [2, 6, 4, 7, 8, 7, 1, 0, 0, 5].

Example 2:

Input:  arr = [-5, 4, -2, 3, 1]
Output: 6 
Explanation:
      Starting with a value of 6 gives the following sums: 6 + -5 = 1 → 1 + 4 = 5 → 5 + -2 = 3 → 3 + 3 = 6 → 6 + 1 = 7. Any initial value less than 6 will fail at the first element.

Constraints:

1 ≤ n ≤ 10^5
-10^6 ≤ arr[i] ≤ 10^6