Check if a subarray with 0 sum exists or not

Posted in

Check if a subarray with 0 sum exists or not
vinaykhatri

Vinay Khatri
Last updated on March 19, 2024

    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++)
        {
            // add the elements
            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[0]);
     
        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
        s.add(0)
    
        #initializing variable sum_ that will store the sum of array elements
        sum_= 0
    
        #traverse through array elements
        for element in arr:
            
            #add the array elements 
            sum_+=element
    
            #check if the sum_ present in the set s
            if sum_ in s:
                return True
    
            # add sum in the set s
            else:
                s.add(sum_)
    
        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).

    People are also reading:

    Leave a Comment on this Post

    0 Comments