# 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:**

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

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; }

Enter array size: 7 Enter array elements: 3 6 8 4 1 7 14 Equilibrium index of array is 4OUTPUT:

**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; }

Enter array size: 7 Enter array elements: 3 6 8 4 1 7 14 Equilibrium index of array is 4OUTPUT:

**Related Posts:**

**Program to find majority element of an Array.****Program to find mean of the Array.****Program to sort an Array of 0s and 1s.****Program to Reverse an Array.****Program to count number of odd numbers and even numbers in an array.****Program to find absolute difference between sum of odd index elements and even index elements.****Program to find smallest and largest element of the array.****Program to count occurrences of a particular element in an array.****Program to search an element in an Array (Linear Search).****Program to Rotate Array Elements by ‘D’ positions.****Program to find most frequent element in an array.****Program to find pair in an array with given sum.****Program to find first repeating element of an array.****Program to merge two sorted arrays.****Program to find missing number in an array.****Program to sort if array is sorted.****Program to print Alternate Elements of an Array.****Program to swap kth element from beginning to kth element from end in an Array.****Program to print all possible subarrays of the given array.****Program to print kth smallest and kth largest element of an Array.**