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)]
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