Find the Equilibrium Index of the Array

Find the Equilibrium Index of the Array” is one of the favorite technical interview problem based on array data structure. Here, we are given an array of size ‘n’ and our task is to find the equilibrium index of an array.

Equilibrium index of an array is that index of array where sum of elements to the left of that index is equal to the sum of elements to the right of that index.

If there is no equilibrium index in the array, simple print ‘-1’.

Example:

INPUT:
Arr[] = {4,5,3,8,7,5}
OUTPUT:
Equilbrium Index: 3
Explanation:
Arr[0]+Arr[1]+Arr[2] = Arr[4] + Arr[5]
4 + 5 + 3 = 7 +5 = 12

There can be multiple methods to find the equilibrium index of the array. Some of them are:

METHOD 1: Brute-Force Solution:

This is the simplest method to find the equilibrium index of the array. Here, we find the sum of left elements and sum of right elements for every element of the array. If we found any index where sum of elements to the left of that index is equal to the sum of elements to the right of that index, then, that index would be equilibrium index of the array.

The time complexity of brute force solution would be O(n^2).

C++ Program to find the equilibrium index of the array is as follows:

/* C++ Program to find the equilibrium index of the array */  
#include<bits/stdc++.h>  
using namespace std;  
int main()  
{  
    /* Scan array size */  
    int n;  
    cout<<"Enter array size: ";  
    cin>>n;  
      
    /*Scan array elements */  
    int arr[n];  
    cout<<"\nEnter array elements:\n";  
    for(int i = 0; i < n; i++)  
    {  
        cin >> arr[i];  
    }  
      
    /* Calculate sum of left elements and 
       sum of right elements for every index */  
    int res = -1;  
    for(int i = 0; i < n; i++)  
    {  
        int left_sum = 0;  
        int right_sum = 0;  
        /* Calculate left sum */  
        for(int j = 0; j < i; j++)  
        {  
            left_sum = left_sum + arr[j];  
        }  
        /* Calculate right sum */  
        for(int j = i+1; j < n; j++)  
        {  
            right_sum = right_sum + arr[j];  
        }  
        if(left_sum == right_sum)  
        {  
            res = i;  
            break;  
        }  
    }  
      
    /* Printing the result */  
    cout<<"\nEquilibrium index of array is "<<res;  
      
}  
OUTPUT:
Enter array size: 7
Enter array elements:
3 6 8 4 1 7 14
Equilibrium index of array is 4

METHOD 2: Optimized Solution

This solution solves the problem in O(n) and without using extra space. 

Here, we find the sum of all the elements of the array, then we iterate the array from right and maintain the right sub-array sum. 

We can calculate the left subarray sum in constant time by subtracting right sub-array sum and current element from total sum.

If at any point, left sub-array sum is equal to right subarray sum, then return that index.

C++ Program to find equilibrium index of the array is as follows:

/* C++ Program to find the equilibrium index of the array */  
#include<bits/stdc++.h>  
using namespace std;  
int main()  
{  
    /* Scan array size */  
    int n;  
    cout<<"Enter array size: ";  
    cin>>n;  
      
    /*Scan array elements */  
    int arr[n];  
    cout<<"\nEnter array elements:\n";  
    for(int i = 0; i < n; i++)  
    {  
        cin >> arr[i];  
    }  
      
    /* Calculate sum of all elements of array */  
    int sum = 0;  
    for(int i = 0; i < n; i++)  
    {  
        sum = sum + arr[i];  
    }  
      
    /* Traversing array from right to left */  
    int res = -1;  
    int right_sum = 0;  
    for(int i = n-1; i >= 0; i--)  
    {  
        /* Calculate sum of left sub-array of current index */  
        /* sum - (arr[i] + right_sum) */  
        int left_sum = sum - (arr[i] + right_sum);  
          
        /* If left_sum == right_sum */  
        if(left_sum == right_sum)  
        {  
            res = i;  
            break;  
        }  
          
        right_sum = right_sum + arr[i];  
          
    }  
      
    /* Printing the result */  
    cout<<"\nEquilibrium index of array is "<<res;  
      
}  
OUTPUT:
Enter array size: 7
Enter array elements:
3 6 8 4 1 7 14
Equilibrium index of array is 4

You may also like...

Leave a Reply

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