Algorithm Code Optimization: Find the Equilibirum: Find an index in an array such that its prefix sum equals its suffix sum

Question

Here's my Task Description:

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] + A1 + ... + 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[0] = -1
A[1] =  3
A[2] = -4
A[3] =  5
A[4] =  1
A[5] = -6
A[6] =  2
A[7] =  1

P = 1 is an equilibrium index of this array, because:
•   A[0] = −1 = A[2] + A[3] + A[4] + A[5] + A[6] + A[7]
P = 3 is an equilibrium index of this array, because:
•   A[0] + A[1] + A[2] = −2 = A[4] + A[5] + A[6] + A[7]
P = 7 is also an equilibrium index, because:
•   A[0] + A[1] + A[2] + A[3] + A[4] + A[5] + A[6] = 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: int solution(NSMutableArray *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.

Here's my Solution for the problem in Objective C:

-(int)solution:(NSArray *) A{
for (int i=0; i<A.count; i++) {

    NSUInteger backwardsTotal = 0;
    if (i > 0) {
        for (int k=0; k<i; k++) {
            NSNumber *kValue = A[k];
            backwardsTotal += kValue.intValue;
        }
    }

    NSUInteger forwardTotal = 0;
    for (int j=i+1; j<A.count; j++) {
        NSNumber *jValue = A[j];
        forwardTotal += jValue.intValue;
    }

    if (backwardsTotal == forwardTotal) {
        return i;
    }
}

return -1;
}

How can i optimise this solution?

Changes made to the method as per @Nikki comments:

-(int)solution:(NSArray *) A{
NSUInteger a = 0, b = 0;

for (int i=0; i<A.count; i++) {
    NSNumber *iValue = A[i];
    b += iValue.intValue;
}
NSLog(@"Total: b: %ld", b);

for (int k=0; k<A.count; k++) {
    NSNumber *kValue = A[k];
    b -= kValue.intValue;

    NSLog(@"b: %ld", b);
    NSLog(@"a: %ld", a);

    if (a == b)
        return k;

    a += kValue.intValue;

}

return -1;
}

I am testing the above code as follows:

//    NSArray *array = @[@"-3", @"0", @"3"];
NSArray *array = @[@"-2", @"4", @"-5", @"6", @"1", @"-6", @"2", @"1"];
NSUInteger one = [self solution:array];
NSLog(@"one: %ld", one);//returns 7

The solution seems to work better. But still, it is not perfect and uses O(N**2) time complexity. And also there are Timeout errors in other Performance tests.

Screenshots below:

Can this be still optimized?

Hint: What do you notice about the value computed for `backwardsTotal`, going from one outer loop iteration to the next? (The same applies for `forwardTotal`.) — j_random_hacker, Sep 02 '15 at 06:58
@CoderSaru: The algorithm as given by matanso is already O(n). It might be the case that you just need to remove your NSLog inside your `solution` method, because printing is time consuming. — justhalf, Jan 24 '17 at 08:09

score 7 · Accepted Answer · answered Sep 02 '15 at 06:59

7

Your current solution is O(n^2) operations (You sum the whole array n times).

You could have just 2 variables at any point, a and b, setting a to zero and b to the sum of the array. Afterwards, iterate over all of the indices. When iterating over index i, first do b -= arr[i]. Then, if a==b, return i. Then do a += arr[i]. That is O(n) operations, much more efficient.

answered Sep 02 '15 at 06:59

matanso

1,274
1
10
16

Hi @Nikki I have updated my Question. Please have a look. – Saru Sep 02 '15 at 17:46

score 1 · Answer 2 · answered Jan 13 '16 at 12:27

How about this, hope it works for ya..

int equi(int arr[], int n) {
if (n==0) return -1; 
long long sum = 0;
int i; 
for(i=0;i<n;i++) sum+=(long long) arr[i]; 

long long sum_left = 0;    
for(i=0;i<n;i++) {
    long long sum_right = sum - sum_left - (long long) arr[i];
    if (sum_left == sum_right) return i;
    sum_left += (long long) arr[i];
} 
return -1; 
}

score 0 · Answer 3 · edited May 23 '17 at 11:53

Official C solution from Codility

http://blog.codility.com/2011/03/solutions-for-task-equi.html

int equi(int arr[], int n) {
    if (n==0) return -1; 
    long long sum = 0;
    int i; 
    for(i=0;i<n;i++) sum+=(long long) arr[i]; 

    long long sum_left = 0;    
    for(i=0;i<n;i++) {
        long long sum_right = sum - sum_left - (long long) arr[i];
        if (sum_left == sum_right) return i;
        sum_left += (long long) arr[i];
    } 
    return -1; 
}

Two points to note:

long long is used to prevent overflow. This is enough because of the minimum size guarantees mentioned at+ https://stackoverflow.com/a/37124098/895245 together with Codility's input
take care of the n==0 special case

Other languages:

Algorithm Code Optimization: Find the Equilibirum: Find an index in an array such that its prefix sum equals its suffix sum

3 Answers3

Linked