Problem Brief

Minimum Absolute Sum

NEW GRADOA

See Google online assessment and hiring insights

There is an array A consisting of N integers. Choose at most one element to multiply by -1 in order to obtain an array whose sum of elements is as close to 0 as possible. That is, find the sum with the minimum absolute value.

that, given an array A, returns the minimum absolute value of the sum of A that can be obtained.

1Example 1

Input

A = [1, 3, 2, 5]

Output

Explanation

For A = [1, 3, 2, 5], after multiplying the last element by -1, A will be equal to [1, 3, 2, -5]. Its sum is 1. It is not possible to obtain any sum closer to 0. The function should return 1.

2Example 2

Input

A = [-4, 0, -3, 3]

Output

Explanation

For A = [-4, 0, -3, 3], we can multiply -4 by -1 and therefore obtain A = [4, 0, -3, 3]. Its sum is 2. The function should return 2.

3Example 3

Input

A = [4, -3, 5, -7]

Output

Explanation

Assume that A = [4, -3, 5, -7]. Its sum is -1. There is no possible move that could improve this result. The function should return 1.

4Example 4

Input

A = [-15, 18, 1, -1, 10, -22]

Output

Explanation

It is optimal to change -1 to 1. The function should return 9.

Constraints

Limits and guarantees your solution can rely on.

N is an integer within the range [1..100,000];
each element of array A is an integer within the range [-1,000..1,000].

Draft autosaves locally

public int minAbsoluteSum(int[] A) {
  // write your code here
}

Input

[1, 3, 2, 5]

Output