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:
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.
Use two loops to implement it in C. Outer loop iterates through all the element and inner loop finds out whether the current index picked by the outer loop is equilibrium index or not. Time complexity of this solution is O(n^2).
#include <stdio.h>
int equilibrium(int arr[], int n)
{
int i, j;
int leftsum, rightsum;
/* Check for indexes one by one until an equilibrium
index is found */
for ( i = 0; i < n; ++i)
{
leftsum = 0; // initialize left sum for current index i
rightsum = 0; // initialize right sum for current index i
/* get left sum */
for ( j = 0; j < i; j++)
leftsum += arr[j];
/* get right sum */
for( j = i+1; j < n; j++)
rightsum += arr[j];
/* if leftsum and rightsum are same, then we are done */
if (leftsum == rightsum)
return i;
}
/* return -1 if no equilibrium index is found */
return -1;
}
int main()
{
int arr[] = {-7, 1, 5, 2, -4, 3, 0};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printf("%d\n", equilibrium(arr, arr_size));
getchar();
return 0;
}
Credit: http://www.geeksforgeeks.org/equilibrium-index-of-an-array/
