Equilibrium index of an Array

Equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes.

Naive Solution:

This solution has time complexity O(n^2). The outer loop selects the index, 0...n-1. The inner loop iterates through all elements and calculates leftsum if the index is to the left (index less than outer index) . It calculates rightsum if the index is to the right(index greater than outer index).

Code:

import java.util.*;

public class Test{

    

  public static void main(String[] args) {

    

    Scanner in = new Scanner(System.in);

    int[] a = {-7,1,5,2,-4,3,0};

    int n = a.length;

    int leftsum = 0;

    int rightsum = 0;

    for(int i=0; i<n; i++){

        leftsum = 0;

        rightsum = 0;

        for(int j=0; j<n; j++){

            if(j<i){

                leftsum += a[i];

            }

            else if(j>i){

                rightsum += a[i];

            }

        }

        if(leftsum == rightsum)

            System.out.print(i+" ");

    }

  }

}

Efficient solution:

Here we initialize the rightsum to sum of the elements and leftsum to zero. Then for each element these values are adjusted accordingly. Let us see this with the code.

Code:

import java.util.*;

public class Test{

    

  public static void main(String[] args) {

    

    Scanner in = new Scanner(System.in);

    int[] a = {-7,1,5,2,-4,3,0};

    int n = a.length;

    int leftsum = 0;

    int rightsum = 0;

    for(int i=0; i<n; i++){

       rightsum+=a[i];

    }

    for(int i=0; i<n; i++){

        rightsum -= a[i];

        if(rightsum == leftsum){

            System.out.print(i+" ");

        }

        leftsum+=a[i];

    }

  }

}

Output:

3 6 

Explanation:

At i=0;

   leftsum = 0; 

  rightsum = 0 (since total is zero) - (-7) = 7   (which is equal to 1+5+2-4+3+0)

  Here,  leftsum != rightsum (0!=7)

At i=1;

   leftsum = -7;(from previous itereation)

   rightsum = rightsum - a[1] = 7-1 = 6   (which is equal to 5+2-4+3+0)

    Here leftsum != rightsum (-7!=6)

At i=2;

    leftsum = -7+1 = -6  (from previous iteration)

    rightsum = rightsum-a[2] = -6-5 = 1

     here also they are not equal

At i =3; 

    leftsum = -6+5 = -1

    rightsum = rightsum-a[3] = 1-2 = -1

    here leftsum and rightsum both are equla to -1. Hence 3 is an equilibrium index. Similarly 6 is also an equilbrium index for this array