Leave a comment

Sub-array with sum zero

Ques: An array contains negative as well as positive numbers in random order, find the first sub array for which the sum of all the elements is zero.

Solution: First of all we need to think how can we find out if the sum of all the elements in a sub array is zero. Let’s take an example :
      a= {5,4,3,-2,-2,-3,7}

If you see, in this array from index 1 to 5 is the sub array with sum zero. By looking at a small array we can tell but, how do we know programmatically? it needs a way to find out.

Just think for a minute. We can easily check the sum of all the elements from start index of the array to ith index. Let say i=5 and total sum from start index of the array to ith index is 27 (Do not refer to array given above, just assume another array). Now, assume that from start index of the array to jth index, let say j=8 total sum is again 27, does it not indicate that from 6th index to 8th index the sum is zero, that’s why the same summation has been repeated. This is the clue, got it?

One more condition is there. Let’s take an another example:
      a = {5,4,1,-3,-7,6}

Can you identify the sub array for which the sum is zero? Of-course you do. From index 0 to 4 the sum is zero but, in this scenario from start index to 4th index there is no duplicate summation. Well, we could find a sub array with sum zero.Does it not indicate that by calculating sum from start index we get zero at some index means, from start index to that index, the sub array is with sum zero. This was the whole logic I could think.

I tried to code the above logic, might modifications are required.


public void findSubarray(int a[],int size)
{
    int sum = 0;
    int sum1 = 0;
    for(int i=0;i<size;i++)     {
        sum = sum+a[i];
        if(sum == 0)
        {
            System.out.println("sum is 0 from index 0 to index"+i);
            return;
        }
        sum1 = 0;
        for(int j=0;j<i;j++)         {
            sum1=sum1+a[j];
            if(sum == sum1)
            {
                System.out.println("sum is zero from index: "+(j+1)+" to index: "+i);
                return;
            }
        }
    }
    System.out.println("no sub array with sum zero...");
}

Time Complexity:
The complexity of this solution is O(n^2) as at each index we are calculating the summation of all previous elements in the array.
Space Complexity:
Space complexity is O(1) as we did not use any extra memory.

We can make a faster solution if we are allowed to use extra memory. In previous solution, we were calculating the summation at each index and then we were checking if till any of the previous index, summation was same as it is at current index. Now, if we could find out if the summation till current index has already been occurred without calculating the summation from 0th index to all previous index, we can reduce our time complexity from n^2 to n. To check if summation has already been occurred in constant time we have to store the summation at each index somewhere so that once we move to next index, we have pre-calculated summation and no need to calculate the summation till all previous index. The best way of holding the summation is hashmap so that we can find out the summation in constant time. Let me take an example. Suppose at ith index summation is 30, you will store in hasmap key as 30 and value as i. Now, let’s say at jth index (j > i) summation is again 30. You will check in map, oh at ith position summation was 30 so from i+1 to j summation of subarray is zero. I am giving a rough implementation, please modify if required:

public void findSubarray(int a[],int size)
{
    int sum = 0;
    int sum1 = 0;
    Map map = new HashMap();
    for(int i=0;i<size;i++)     {
        sum = sum+a[i];
        if(sum == 0)
        {
            System.out.println("sum is 0 from index 0 to index"+i);
            return;
        }
        if(map.get(sum) != null){
            System.out.println("sum is zero from: "+map.get(sum)+" to :"+i);
            return;
        }
        map.put(sum, i);
    }
    System.out.println("no sub array with sum zero...");
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: