Equilibrium index of a sequence 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 a sequence 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:
A[0]+A[1]+A[2]+A[3]+A[4]+A[5]=0
(sum of zero elements is zero) 7 is not an equilibrium index, because it is not a valid index of sequence A.
Assume the sum of zero elements is equal zero. Write a function
int equi(int[] A);
that given a sequence, returns its equilibrium index (any) or -1 if no equilibrium indexes exist. Assume that the sequence may be very long.
Solution:
1. First get the sum of all the numbers in the array first. sum
2. adding the array from the left one by one. tempSum
3. if the sum – tempSum – A[i] == tempSum, then i is an equibibrium index.
int equip(int[] A){
int sum = sum(A);
int tempSum = 0;
for(int i=0;i<A.length;i++){
if(sum - tempSum - A[i] == tempSum){
return i;
}
tempSum += A[i];
}
return -1;
}
long sum(int [] A){
int sum = 0;
for(int i=0;i<A.length;i++){
sum += A[i];
}
}
The best solution, which are very often available should be the O(N) complex one. Always try to find the solution with O(N) time complexity or less.