# 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;
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;
// 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 = {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
```