FastPrep
Problem · Array

Minimum Start Value

Learn this problem
● EasyGoldman SachsFULLTIMEOA

Problem statement

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

minStart(arr: int[]) → long

Complete the function minStart in the editor.

minStart has the following parameter(s):

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

Returns

long: the minimum initial value

Examples

Example 1

arr = [-5, 4, -2, 3, 1, -1, -6, -1, 0, 5]return = 8
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

arr = [-5, 4, -2, 3, 1]return = 6
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

More Goldman Sachs problems

drafts saved locally
public long minStart(int[] arr) {
    // write your code here
}
arr[-5, 4, -2, 3, 1, -1, -6, -1, 0, 5]
expected8
checking account