# Find Equilibrium Index of an Array

Find Equilibrium Index of an Array” is one of the favourite technical interview problem based on array data structure. Here, we are given an array of size ‘n’ and our task is to find 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 (Find equilibrium index of an array):

```INPUT:
Arr[] = {4,5,3,8,7,5}
OUTPUT:
Equilbrium Index: 3
Explanation:
Arr+Arr+Arr = Arr + Arr
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 to find equilibrium index of an array:

This is the simplest method to find equilibrium index of an 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 equilibrium index of an array is as follows:

```/* C++ Program to find equilibrium index of an 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 to find equilibrium index of an array

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 an array is as follows:

```/* C++ Program to find equilibrium index of an 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```

Related Posts: