Sunday, August 18, 2013

Find the equilibrium position of an array

Problem:
write a code to find the equilibrium position of the array.

given an array: 3,-3,8,6,-1,-5

equilibrium position should be 2(element 8) sum of lower index(3+-3)=sum of higher index(6+(-1)+(-5))

Solution:
For any index i, if we know the sum of items 0..i, we can find the sum of items i+1..n-1 by subtracting it from the sum of all elements. So:
1. Find the total sum of the array
2. For each element in the array
2.a. keep contSum, which is the sum up to the point in the array
2.b. if the (sum - A[i] - contSum) == contSum, return index (This is the point where the leftSum and the rightSum equals)
3. Return -1 if not found

public static int equilibriumIndex(int[] A) {
 int sum = 0;
 int i = 0;
 for (i = 0; i < A.length; i++) 
  sum += A[i];
  
 int contSum = 0;
 for (i = 0; i < A.length; i++) {
  if ( (sum - A[i] - contSum) == contSum) return i;
   
  contSum += A[i];
 }
  
 return -1; // not found
}


Complexity:
time - O(n)
space - O(1)
Links and credits:
http://www.careercup.com/question?id=23088665

No comments:

Post a Comment