Vua Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua! Sunday, November 20, 2016

Find an index in an array such that its prefix sum equals its suffix sum.

A zero-indexed array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e.
A + A + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].
Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N−1.
For example, consider the following array A consisting of N = 8 elements:
A = -1 A = 3 A = -4 A = 5 A = 1 A = -6 A = 2 A = 1
P = 1 is an equilibrium index of this array, because:
• A = −1 = A + A + A + A + A + A
P = 3 is an equilibrium index of this array, because:
• A + A + A = −2 = A + A + A + A
P = 7 is also an equilibrium index, because:
• A + A + A + A + A + A + A = 0
and there are no elements with indices greater than 7.
P = 8 is not an equilibrium index, because it does not fulfill the condition 0 ≤ P < N.
Write a function:
class Solution { public int solution(int[] A); }
that, given a zero-indexed array A consisting of N integers, returns any of its equilibrium indices. The function should return −1 if no equilibrium index exists.
For example, given array A shown above, the function may return 1, 3 or 7, as explained above.
Assume that:
• N is an integer within the range [0..100,000];
• each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
Complexity:
• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

---------------------------------------------------------------------------------------------------------------
Solution:

`import java.math.BigInteger;public class Solution {    private static BigInteger sub = BigInteger.ZERO;    private static BigInteger sum = BigInteger.ZERO;    private static BigInteger left = BigInteger.ZERO;    private static BigInteger right = BigInteger.ZERO;    public static void main(String[] args) throws Exception {        Solution s = new Solution();        int[] A = {-1, 3, -4, 5, 1, -6, 2, 1};        System.out.print(s.solution(A));    }    public int solution(int[] A) {        sum = BigInteger.ZERO;        if (A.length != -1 ) {            sum = sum.add(sumOfSubArray(A));        }        for (int i=0; i<A.length; i++) {            sub = sub.add(BigInteger.valueOf(A[i]));            left = sub.subtract(BigInteger.valueOf(A[i]));            right = sum.subtract(sub);            if ( left.equals(right)) {                return i;            }        }        return -1;    }    public static BigInteger sumOfSubArray(int[] a) {        BigInteger sum = BigInteger.ZERO;        for (int i = 0; i < a.length; i++) {            sum = sum.add(BigInteger.valueOf(a[i]));        }        return sum;    }}` 