Skip to main content

Print all subarrays with 0 sum

Here given code implementation process.

//C++ Program 
//Print all subarrays with 0 sum
//compile code like this
//g++ -std=c++11 test.cpp
//here test.cpp is file name
#include <iostream>
#include <map>
#include <vector>

using namespace std;
//This is finding the all subarrays of zero sum in array
void zero_sum(int collection[], int size)
{
	//Define a map which is is an integer and that is capable to collect 
	//Group of integer value [like a vector of integer]
	map < int, vector < int > > mp;
	//This is collect information of resultant location
	vector < pair < int, int > > result;
	vector < int > ::iterator it;
	int current_sum = 0;
	int i = 0;
	//loop are collecting the information of zero sum subarray
	for (i = 0; i < size; ++i)
	{
		//Sum the array elements  which is exist on ith location
		current_sum += collection[i];
		if (current_sum == 0)
		{
			//base case when index 0 to i sum is zero
			result.push_back(make_pair(0, i));
		}
		if (mp.find(current_sum) != mp.end())
		{
			//When current sums already exist in map collection
			for (it = mp[current_sum].begin(); it != mp[current_sum].end(); it++)
			{
				//Add new pair into resultant vector
				//(*it) is a previous index which are same sum, 
				//add new pair (*it +1) to current element location [i]
				result.push_back(make_pair( *it + 1, i));
			}
		}
		//Add new sum and location into map
		mp[current_sum].push_back(i);
	}
	cout << " Zero sum subarray is None : ";
	if (result.size() == 0)
	{
		cout << "None" << endl;
	}
	else
	{
		//Display resultant index
		for (auto out_value = result.begin(); out_value != result.end(); out_value++)
		{
			cout << "\n [";
			for (int i = out_value->first; i <= out_value->second; ++i)
			{
				cout << "(" << collection[i] << ")";
				if (i < out_value->second)
				{
					cout << " + ";
				}
			}
			cout << "]";
		}
	}
}
int main()
{
	//Define collection of integer elements
	//This is an input array
	int collection[] = {
		1 , 4 , -5 , 3 , 2 , -5 , 7 , -2
	};
	//Get the size of array
	int size = sizeof(collection) / sizeof(collection[0]);
	//Find the sum of resulting to zero subarray
	zero_sum(collection, size);
	return 0;
}

Output

 Zero sum subarray is None :
 [(1) + (4) + (-5)]
 [(-5) + (3) + (2)]
 [(1) + (4) + (-5) + (3) + (2) + (-5)]
 [(3) + (2) + (-5)]
 [(-5) + (3) + (2) + (-5) + (7) + (-2)]
 [(-5) + (7) + (-2)]




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment