C++ Program to Find if there is any subarray with sum equal to 0

October 11, 2022

Subarray with sum equal to Zero in C++

Here, in this page we will discuss the program to find if there is any subarray with sum equal to zero in C++ programming language. If such subarray is present then print true otherwise print false.

Method Discussed :

Method 1 : Naive Approach
Method 2 : Using Hashing

Method 1 :

Run a outer loop for index 0 to n.
Run a nested loop from index i+1 to n,
Find sum, if it is equal to 0, then print true.
Otherwise, print false.

Time and Space Complexity

Time Complexity : O(n²)
Space Complexity : O(1)

Run

#include<bits/stdc++.h>
using namespace std;

int main(){
    int arr[] = {-3, 2, 3, 1, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    int flag = 0, sum;
    
    for(int i=0; i<n; i++){
      
        for(int j=i; j<n; j++){
            sum += arr[j];
            
            if(sum==0){
                flag =1;
                break;
            }
        }
    }
    
    if(flag==1)
    cout<<"true";
    
    else cout<<"false";
    
}

Output

false

Method 2 :

Iterate through the array and for every element arr[i],
Calculate the sum of elements from 0 to i.
If the current sum has been seen before, then there is a zero-sum array.
Hashing is used to store the sum values so that we can quickly store sum.
Check out whether the current sum is seen before or not.

Time and Space Complexity

Time Complexity : O(n²)
Space Complexity : O(1)

Run

#include<bits/stdc++.h>
using namespace std;

int main(){
    int arr[] = {-3, 2, 3, 1, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int flag = 0, sum = 0;
    
    set<int>st;
    
    for(int i=0; i<n; i++){
        
         sum += arr[i];
         if (sum == 0 || st.find(sum) != st.end()){
            flag=1;
            break;
         }
 
        st.insert(sum);
    }
    
    
    if(flag==1)
    cout<<"true";
    
    else cout<<"false";
    
}