- 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.

^{2})

**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.

## 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