Pages

Friday, November 5, 2010

Equilibrium index

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.

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
import java.util.Hashtable;

public class EquilibriumIndex {

    // this return the first one, order N (linear)
    int equi(int[] A) {
        Hashtable table = new Hashtable();
        int leftSum = 0, totalSum = 0;
        for (int i = 0; i < A.length; i++) {
            totalSum += A[i];
            int key = (2 * leftSum) + A[i];
            if (!table.containsKey(key)) //we are only concerned about the first index
                table.put(key, i);
            leftSum += A[i];
        }
        return table.get(totalSum) == null ? -1 : table.get(totalSum); // just get the first occurrence
    }
}

TEST

import java.util.Arrays;

public class TestEquilibriumIndex {
    public static void main(String[] args) {
        EquilibriumIndex ei = new EquilibriumIndex();
        int[] A = { -7, 1, 5, 2, -4, 3, 0 };
        System.out.println("For the array: " + Arrays.toString(A));
        System.out.println("The first Equilibrium Index: " + ei.equi(A));
    }
}

No comments :