# Check if a subarray with 0 sum exists or not

Posted in  Vinay Khatri
Last updated on September 23, 2023

## Problem Statement

Let us say that we have given an array ``` arr. ``` We need to check if any subarray of the array ``` arr ``` has a sum value of 0. If it does, then it should print the statement " ``` Subarray with zero-sum exists ``` ". On the other hand, if there is no subarray with sum 0, then it must print the statement " ``` Subarray with zero-sum does not exists ``` " .

Example:

Sample test 1

``````arr = [1,2,-3, 4, 7,-6, -10]
Output: Subarray with zero-sum exists``````

Explanation In the above array ``` arr ``` , there are some subarrays, with each subarray having a sum equal to 0.

``````[1,2,-3]
[4,2,-6]
[3,7,-10]``````

As you can see, the sum of each subarray is 0.

Sample test 2

``arr = [1,2,3,4,-12,-13]``
```
Output: ```
``Subarray with zero-sum does not exists``

Explanation In the above array, there is no such subarray that has a sum equal to 0. And that's why it prints the statement ``` Subarray with zero-sum does not exists ``` .

## Solution

To solve the problem we can use the set hashing technique, which is explained as follows:

• Using the set hashing, we will first create an empty set ``` s ``` that contains only unique elements in the given array.
• Insert ``` 0 ``` in the set ``` s ``` .
• Now, we will traverse through every element of the array ``` arr ``` and keep adding the array elements with each iteration. Also, we will store the resulting value in the variable ``` sum ``` .
• In each iteration, we will check if the value of ``` sum ``` already exists in the set ``` s. ```
• If yes, we will return 'True' and print the statement ``` Subarray with zero-sum exists. ```
• If the loop gets completed  and no value of sum is in the array, we will return 'False' and print the statement ``` Subarray with zero-sum does not exists. ```

The basic idea is that if the prefix sum of the array is already present in the set ``` s ``` , it means the array contains a subarray that has a sum equal to zero.

Example

The prefix sum of the array ``` [1,2,-3, 4, 7,-6, -10] ``` is ``` [1,3,0,4,11,5,-5] ``` . In this prefix sum, we are getting an element 0 which already exists in the set ``` s ``` . Not only zero, but if two common prefix sum comes in an array, this means the array contains a zero-sum subarray. The two common prefix sum indicates that the sum of the elements between those prefix sum is zero.

## C++ Code to Check if a Subarray with 0 Sum Exists or Not

``````#include <iostream>
#include <set>
using namespace std;

// boolean Function to check if subarray with zero-sum is present in a given array or not
bool hasSumZeroSubarray(int arr[], int n)
{
// create an empty set s that will store the prefix sum of array elements
set <int> s;

// insert 0 into set s
s.insert(0);

//elements prefix sum
int sum = 0;

// traverse the given array
for (int i = 0; i < n; i++)
{
sum += arr[i];

// check if sum is already present in the set s
if (s.count(sum)) {
return true;
}
else {
// insert the sum into set if sum is not present in the set
s.insert(sum);
}
}

// if there is no subarray with sum 0
return false;
}

int main()
{	//given array
int arr[] = {1,2,-3, 4, 7,-6, -10};

//size of the array
int n = sizeof(arr)/sizeof(arr);

if(hasSumZeroSubarray(arr, n))
{
cout << "Subarray with zero-sum exists";
}
else
{
cout << "Subarray with zero-sum does not exists";
}

return 0;
}``````

### Output ## Python Code to Check if a Subarray with 0 Sum Exists or Not

``````def hasSumZeroSubarray(arr, n):
#create an empty set s
s= set()

#insert 0 as the first element into set s

#initializing variable sum_ that will store the sum of array elements
sum_= 0

#traverse through array elements
for element in arr:

sum_+=element

#check if the sum_ present in the set s
if sum_ in s:
return True

# add sum in the set s
else:

return False

if __name__ =="__main__":
#given array
arr= [1,2,-3, 4, 7,-6, -10]

#size of the array
n = len(arr)

if hasSumZeroSubarray(arr,n):
print("Subarray with zero-sum exists")
else:
print("Subarray with zero-sum does not exists")``````

### Output ## Complexity

• Time Complexity: O(N) : The time complexity of the above programs is O(N), where N is the total number of elements present in the array. The time complexity is linear because we are going through the array list only once.
• Space Complexity: O(N): The space complexity of the above algorithms is also O(N) because we are using a set that can also have N number of elements.

## Conclusion

To check if a subarray with 0 sum exists or not is one of the most common programming problems. In this tutorial, we have only covered the set hashing technique to check if an array contains any subarray with sum zero that leads to the time complexity of O(N).

You can also use the brute force or naive approach where you have to find out all the subarrays of an array and check if any of the subarrays has a sum equal to zero. The time complexity of that algorithm would be O(N^N).