Find A Subarray With 0 Sum

Let's start by understanding the problem statement of this task.

You are given an array, your work is to find out if there is any subarray or not with sum as 0.

Hint:

For solving the above algorithm, we need to solve it using the unordered set, so as to find the elements in the set randomly in the given range rather than finding it index by index.

Quick Think:

For solving the above algorithm, we need to ponder over the following steps:-

• The unordered set has to be used to solve the above algorithm.
• If the sum of the elements in a certain range is 0 then check for the resultant sum in the set.

Algorithm:

Declare a function to check for the sum of the subarray as 0 with arguments as the array and the size of the array, and follow the steps below to reach the final output:

Step1: Declare an unordered set of integer type.

Step2: Traverse the array and keep summing the numbers present in the array and check if the sum is equal to 0 or the resultant sum is present in the set is yes, then return true else go to step 3.

Step3: Insert the sum into the set.

Implementation Of The Above Algorithm:

Now let's see the implementation of the above algorithm,

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

bool sumzero(int arr[], int n)
{
	unordered_set<int> set;

	/*Traverse through array and store prefix sums. */
	int sum = 0;
	for (int i = 0; i < n; i++)
	{
		sum = sum + arr[i];

		/*If prefix sum is 0 or it is already present. */
		if (sum == 0 || set.find(sum) != set.end())
			return true;

		set.insert(sum);
	}

	return false;
}

/*Driver code to check the above algorithm. */
int main()
{
	int arr[] = { 4, 2, -3, 1, 6 };

	int n = sizeof(arr) / sizeof(arr[0]);
	if (sumzero(arr, n))
		cout << "Found a subarray with 0 sum";
	else
		cout << "No Such Sub Array Exists!";
	return 0;
}

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

The output of the above algorithm is: Found a subarray with 0 sum.

Explanation Of The Above Algorithm:

After declaring the function and the set, we will follow the steps below to reach the output by considering the example shown in the above diagram.

• Now, the first element in the array is 4, so the sum becomes 4 and the sum is inserted into the set since the sum is not equal to 0 as shown in the diagram above.

• Next element is 2 so, the sum becomes 6 and the sum is not equal to 0 so, the sum is pushed into the set as shown in the diagram above.

• Moving on to the next element, we have -3 and hence the sum becomes 3 and the sum is not equal to 0 so, the sum is pushed into the set as shown in the diagram above.

• Moving on to the next element we have 1 and hence the sum becomes 4 and the sum is not equal to 0 but the sum ID present in the set and hence, we will return true as shown in the diagram above which will be our required output.