{"post":"

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:

Start a loop.
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.
As soon as the sums become equal, you have your equilibrium point.

Code:

#include <bits/stdc++.h>\nusing namespace std;\nint equilibriumPoint(int arrEquil[], int size)
\n{\nint outerIterator, innerIterator;\nint lef, righ;
\nfor (outerIterator = 0; outerIterator &lt; size; ++outerIterator)\n{\n\tlef = 0;\t// sum of elements to the left\n\tfor (innerIterator = 0; innerIterator &lt; outerIterator; innerIterator++)\n\t\tlef += arrEquil[innerIterator];\n\n\trigh = 0;\t// sum of elements to the right\n\n\tfor (innerIterator = outerIterator + 1; innerIterator &lt; size; innerIterator++)\n\n\t\trigh += arrEquil[innerIterator];\n\n\tif (lef == righ)\n\n\t\treturn outerIterator;\n}\nreturn -1;\n
\n}
\nint main()\n{\nint arr[] = { 1, 2, 3, 4, 3, 2, 1 };\ncout << \"Equilibrium point is index\" << equilibriumPoint(arr, 7);\nreturn 0;\n}

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 :

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

Code:

#include <bits/stdc++.h>\nusing namespace std;\nint equilibriumPointOptimized(int arr[], int size)
\n{\nint total = 0;\nint lef = 0;\nfor (int iterator = 0; iterator< size; ++iterator)\ntotal += arr[iterator];
\nfor (int iterator = 0; iterator&lt; size; ++iterator)\n{\n\ttotal -= arr[iterator];\n\tif (lef == total)\n\t\treturn iterator;\n\tlef += arr[iterator];\n}\nreturn -1;\n
\n}
\nint main()\n{
\nint arr[] = { 1, 2, 3, 4, 3, 2, 1 };\ncout &lt;&lt; \"Equilibrium point is index \" &lt;&lt; equilibriumPointOptimized(arr, 7);\n\nreturn 0;\n
\n}

Output:

Equilibrium point is index 3

Time Complexity: O(N)

Space Complexity: O(1)

This is how we solve the Equilibrium Point problem.

\n","title":"Equilibrium index of an array","authorDetails":{"name":"Anshuman Raina","slug":"anshuman-raina"},"seo":{"title":"Equilibrium index of an array"},"description":"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.","slug":"find-equilibrium-index-of-an-array-problem/","articleId":"636a83447bb1ce5072622b7e","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}