Minimum Positive Starting Value
Booking.com● EasyFULLTIMEOAProblem statement
Choose a positive integer x. Start a running sum at x and add the values of arr in order. The running sum must be at least 1 after every addition.
Return the smallest possible starting value. Use a 64-bit result because the answer may exceed the 32-bit integer range.
Function
minStartingValue(arr: int[]) → longExamples
Example 1
arr = [-4,3,2,1]return = 5Starting at5 gives running sums1,4,6,7. Starting at4 would reach0 after the first value, so5 is the minimum.
Example 2
arr = [3,-6,5,-2,1]return = 4Starting at4 gives running sums7,1,6,4,5. A smaller start would fall below1 after the second value.
Constraints
- 1 <= arr.length <= 10^5.
- -10^6 <= arr[i] <= 10^6.