Program to Find a Sub Array Whose Sum is Zero

  • Write a program to find a sub array whose sum is equal to 0.

Given an integer array of size N. We have to find a sub array whose sum of elements is equal to 0. Sub array can be of any length, from 1 to N elements. There may be more than one zero sum sub array but we have to print any one.
For Example :
Input Array : 2 6 -4 8 -4 3 10 7 11 9
Output : Zero sum sub array from index 2 to 4

Method 1 : Brute Force
Let inputArray be an integer array of size N.
  • Here, we will check the sum of all possible sub arrays of inputArray using two for loops.
  • Outer for loop will fix one element(let's say K) and inner for loop will find the sum of all sub arrays starting from K.
  • If sum of any sub array is zero, then we found one zero sum sub array.
Time Complexity : O(n2)
Method 2 : Using Hashing
Let inputArray be an integer array of size N.
  • Let the sum of sub array from index i to j is zero. It means the sum of elements from 0 to i-1 is equal to sum of elements from 0 to j. Hence we will try to find two indexes i, and j whose commutative sum from first element is same.
  • We will use a hash table to store the value of commutative sum of all sub array from 0 to i. It will be used to check whether we found any sub array earlier with given sum.
  • Traverse inputArray from index 0 ti N-1 and find sum of all elements from 0 to i.
  • If current sum is already stored in hash table then we found an zero sum array, else store current index in hash table at a slot corresponding to current sum.
Time Complexity : O(n)

C program to find zero sum sub array

#include <stdio.h>

void getZeroSumSubarray(int *array, int size) {
    int hashTable[10000];
    int i, j, sum = 0;       
    
    /*Initialize hash table */
    for(i=0; i<10000; i++) hashTable[i] = -1;
    
    /* Initialize HashTable zero slot with 0 
    because sum of an empty array is 0*/
    hashTable[0] = 0;
    // Traverse through the given array
    for(i = 0; i < size; i++) {   
        sum += array[i];
             
        /* If current element if 0, we found a zero
 sum subarray of size 1 */
 if(array[i] == 0) {
     printf("Zero Sum Sub Array Found from index %d to %d\n", i, i);
     return;
 }
   
        if(sum == 0 || hashTable[sum] != -1) {
            printf("Zero Sum Sub Array Found from index %d to %d\n", hashTable[sum]+1, i); 
        }
  
        /* Add current sum to HashTable */ 
        hashTable[sum] = i;
    }    
    return;
}  

int main(){
    int array[10] = {2, 6, -4, 8, -4, 3, 10, 7, 11, 9}; 
    int i;
    
    getZeroSumSubarray(array, 10);

    return 0;
}
Output
Zero Sum Sub Array Found from index 2 to 4
Posted by
Labels: ,