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[0] + A[1] + ... + 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.
int solution(int A[], int N) {
    // return 3 for [3,2,-5,1]
    int sum_prefix = 0;
    int sum_suffix = 0;
int i, j;
for (i = 0; i < N; i++) {
    // Check if is is the equilibrium point
    sum_prefix = 0;
    for (j = 0; j < i; j++) {
       sum_prefix += A[j];
    }
    sum_suffix = 0;
    for (j = i+1; j < N; j++) {
        sum_suffix += A[j];
       // Compute suffix sum
    }
    if (sum_prefix == sum_suffix)
        return i;
}
return -1;
}

Leave a Reply

Your email address will not be published. Required fields are marked *