Monday, June 1, 2015

Equilibrium point of an array

Problem: Equilibrium point 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.

Solution: Get total sum of array first. Then Iterate through the array and keep updating the left sum which is initialized as zero. In the loop, we can get right sum by subtracting the elements one by one. 
Compare left and right sum, if they are equal then current index is the equilibrium point.

Implementation:

int equilibriumPoint(int arr[], int len)
{
if(len == 0)
return -1;
int sum = 0;
for(int i = 0; i < len; ++i)
sum += arr[i];

int leftSum = 0;
for(int i = 0; i < len; ++i)
{
sum -= arr[i];
if(leftSum == sum)
return i;
leftSum += arr[i];
}
return -1;
}

Complexity: O(n)

No comments:

Post a Comment