C++ program to Check if a subarray with sum 0 exists or not

In this tutorial, We will learn how to check and if there exists any subarray with sum equals to zero or not in C++.

Implement a C++ program to check if an integer array contains any subarray with sum 0. If yes then return “Such subarray exist” else return “Such subarray does not exist”.

EXAMPLE:

INPUT, A: { 4, 7, -2, 3, 4, -5, 1 }

OUTPUT: Such subarray exist

Explanation:

Subarray { 4, -5, 1 } has sum is equal to zero.

Hash:

  • Hash Table is a data structure that is used to store key and value pairs.
  • It is designed to efficiently solve the problem which requires finding and storing an item in the collection.
  • It is useful to scale down the search while looking for an item in the map.
  • Hashing is faster than searching lists and arrays.
  • It provides a more definitive and adaptive method of data retrieval than other data structures.

Check if a subarray with sum 0 exists or not in C++

A naive approach to solve this problem is by finding all the subarray and look for a subarray with sum 0. The time complexity of this approach is O(n^2). The efficient way to do so is by using Hashing.

Firstly, We have to iterate throughout the array and calculate the sum of the elements of the array 0 to the current iteration.

Hashing will store the sum values to make it easier for us to store and search the current sum value. After every iteration, We will check if the current sum already exists in the set or not.

If the current sum already exists, We will return “Such Subarray Exist”.

After complete iteration, if the current sum does not match the existing ones. Return “Such subarray does not exist”.

Implementation of the above approach in C++ is as follows:

#include <bits/stdc++.h>
using namespace std;
bool checkSubArr(vector<int> A)
{
    //initialize sum as 0
    int sum = 0;
    
    //declare hash to store sum
    unordered_set<int> hash;
    hash.insert(0);
    //traverse through array
    for (int i = 0; i < A.size(); i++)
    {
        //current sum
        sum += A[i];
        
        //Check if sum already exists or equal to 0
        if (sum == 0|| hash.find(sum) != hash.end())
            return true;
            
        //store sum in hash
        hash.insert(sum);
    }
    return false;
}
int main()
{
    vector<int> A = { 4, 7, -2, 3, 4, -5, 1 };
    //call func and print Subarray exist if it returns true
    //else print such subarray doesn't exist
    //Conditional statement
    checkSubArr(A)? cout << "Such subarray exist": cout << "Such subarray does not exist";
    return 0;
}

Output:

Such subarray exist

The time complexity of the above algorithm is O(n).

Also, refer:

Leave a Reply

Your email address will not be published. Required fields are marked *