Equilibrium index of an array is an index such that sum of elements at lower indexes is equal to sum of the elements at higher indexes.
For example: in an array {-7, 1, 5, 2, -4, 3, 0}, 3 and 6 are the equilibrium indexes.
Write a function equilibrium(int a[], int n) that prints all equilibrium indexes if present .
Time complexity should be O(n).
For example: in an array {-7, 1, 5, 2, -4, 3, 0}, 3 and 6 are the equilibrium indexes.
Write a function equilibrium(int a[], int n) that prints all equilibrium indexes if present .
Time complexity should be O(n).
#include
ReplyDeletevoid equilibrium(int arr[], int n)
{
int sum = 0; // initialize sum of whole array
int leftsum = 0; // initialize leftsum
int i;
/* Find sum of the whole array */
for (i = 0; i < n; ++i)
sum += arr[i];
for( i = 0; i < n; ++i)
{
sum -= arr[i]; // sum is now right sum for index i
if(leftsum == sum)
printf("%d ",i);
leftsum += arr[i];
}
/* If no equilibrium index found, then return 0 */
return;
}
int main()
{
int arr[] = {-7, 1, 5, 2, -4, 3, 0};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printf("Equilibrium Positions are\n");
equilibrium(arr, arr_size);
return 0;
}