Friday, June 8, 2012

Find sub-sequence within array with sum = 0

A few days ago, I have been given a problem to find the sub-sequence within an array with which has a total sum of 0. Within array A[1-N], you have to find i and j such that
 A[i] + A[i+1]... A[j] = 0; i <=j.

Ofcourse, the problem can be extended further to find the longest subsequence among all possible sub-sequences. Once you have the solution for first part, finding longest sub-sequence is no more a tricky job.


This is what I thought:

The idea is: If sum of elements from [i+1, j] is 0, then, after this subset, ith number would appear again at [j+1] position.



i.e. Sum(N[i] + N[i+1, j]) = N[j + 1], if N[i+1, j] = 0.


FindZeroSumSequence(Array):
{

   1. Sum elements such that ith index has sum up to [0 -i] elements
       For i = 1 to N
       Array[i] += Array[i -1]

   2. Find the first duplicate index from array
       EndIndex = FindFirstDuplicateIndex(Array)


   3. IF EndIndex > -1
       Find the First index with value equal to Array[EndIndex]
       For i = 0 to N
         IF(Array[i] == Array[EndIndex]
           StartIndex = i
           Break


   4. Return StartIndex and EndIndex as sub array indexes.
}



Running time of the algorithm is O(n) (though it slowly depends on the running time of FindFirstDuplicateIndex method which could be implemented in O(n) time).