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[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 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:
- 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 count total number of words in a string.
- Program to find smallest and largest word of the String.
- Program to find Most Frequent Character of the String.
- Program to Remove all the blank spaces from the String.
- Program to check if String is isogram or not.
- Program to Reverse Each word of the String.
