Problem Brief
Minimum Start Value
FULLTIMEOA
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
1Example 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].
2Example 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
Limits and guarantees your solution can rely on.
1 ≤ n ≤ 10^5-10^6 ≤ arr[i] ≤ 10^6