Check if subarray with 0 sum is exists or not

Given an array of integers, check if array contains a sub-array having 0 sum.

 

For example,


Input:  { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 }

Output: Subarray with 0 sum exists

Reasoning: Sub-arrays with 0 sum are

{ 3, 4, -7 }
{ 4, -7, 3 }
{ -7, 3, 1, 3 }
{ 3, 1, -4 }
{ 3, 1, 3, 1, -4, -2, -2 }
{ 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 }

 


 

We can easily solve this problem in linear time by using hashing. We can use set to check if sub-array with zero sum is present in the given array or not. We traverse the given array, and maintain sum of elements seen so far. If sum is seen before (i.e. sum exists in set), we return true as there exists at-least one sub-array with zero sum which ends at current index else we insert the sum into the set.

C++

Download   Run Code


Output:


Subarray exists

Java

Download   Run Code


Output:


Subarray exists


 

The time complexity of proposed solution is O(n) and auxiliary space used by the program is O(n).

 

 
 
Exercise: Extend the solution for non-zero sum of sub-array.

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz