Equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. For example, in an arrya A:

Median of two sorted arrays

A[0] = -7, A[1] = 1, A[2] = 5, A[3] = 2, A[4] = -4, A[5] = 3, A[6]=0

3 is an equilibrium index, because:

A[0] + A[1] + A[2] = A[4] + A[5] + A[6]

6 is also an equilibrium index, because sum of zero elements is zero, i.e., A[0] + A[1] + A[2] + A[3] + A[4] + A[5]=0

7 is not an equilibrium index, because it is not a valid index of array A.

Write a function int equilibrium(int[] arr, int n); that given a sequence arr[] of size n, returns an equilibrium index (if any) or -1 if no equilibrium indexes exist.

Solution : Iterate through the array and find the sum of all elements, lets call it WholeSum. Then start iterating from left to right, while iterating store the addition of the elements in another variable called left sum. From WholeSum we subtract LeftSum and we get RightSum, if LeftSum is equal to RightSum, that s out Equilibrium index of the array. It takes O(n).