what is the best algorithm to use for this problem
- by slim
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.
If you still have doubts, this is a precise definition: the integer k is an equilibrium index of a sequence if and only if and .
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.