Equilibrium index of an array

Find Equilibrium index of an array Problem

PROBLEM: Find the index in the array, which acts as the equilibrium i.e. the sum of the elements of the lesser index than equilibrium is equal to the sum of elements after the equilibrium.

# Brute Force

Pseudo Code:

1. Start a loop.
2. Inside the loop calculate both the sum of elements till the left of the index and the sum of elements to the right of the index.
3. As soon as the sums become equal, you have your equilibrium point.

Code:

#include <bits/stdc++.h>
using namespace std;
int equilibriumPoint(int arrEquil[], int size)
{
int outerIterator, innerIterator;
int lef, righ;
for (outerIterator = 0; outerIterator &lt; size; ++outerIterator)
{
	lef = 0;	// sum of elements to the left
	for (innerIterator = 0; innerIterator &lt; outerIterator; innerIterator++)
		lef += arrEquil[innerIterator];

	righ = 0;	// sum of elements to the right

	for (innerIterator = outerIterator + 1; innerIterator &lt; size; innerIterator++)

		righ += arrEquil[innerIterator];

	if (lef == righ)

		return outerIterator;
}
return -1;

}
int main()
{
int arr[] = { 1, 2, 3, 4, 3, 2, 1 };
cout << "Equilibrium point is index" << equilibriumPoint(arr, 7);
return 0;
}

Output:

Equilibrium point is index 3

Time Complexity: O(N2)

Space Complexity:  O(1)

# Optimized Approach

Pseudo Code:

If we decrease one loop, we can lessen the time complexity. This can be done by :

1. We calculate the total sum of the array.
2. We iterate over the array, and subtract the current array by total sum. This gives us the sum of elements to the right.
3. We add the current array to a variable too. This gives us the left sum.
4. These sums are checked, and when equal give us the equilibrium point.

Code:

#include <bits/stdc++.h>
using namespace std;
int equilibriumPointOptimized(int arr[], int size)
{
int total = 0;
int lef = 0;
for (int iterator = 0; iterator< size; ++iterator)
total += arr[iterator];
for (int iterator = 0; iterator&lt; size; ++iterator)
{
	total -= arr[iterator];
	if (lef == total)
		return iterator;
	lef += arr[iterator];
}
return -1;

}
int main()
{
int arr[] = { 1, 2, 3, 4, 3, 2, 1 };
cout &lt;&lt; "Equilibrium point is index " &lt;&lt; equilibriumPointOptimized(arr, 7);

return 0;

}

Output:

Equilibrium point is index 3

Time Complexity:  O(N)

Space Complexity:  O(1)

This is how we solve the Equilibrium Point problem.