- 0
Notifications Mark All Read
- Login
- Get Prime
Print All Subarrays With 0 Sum in C++
Print all subarrays with 0 sum
Here, on this page, we will discuss the program to Print all subarrays with 0 sum in C++ Programming language.
A simple solution is to consider all subarrays one by one and check if sum of every subarray is equal to 0 or not. The complexity of this solution would be O(n^2).A better approach is to use Hashing.
Algorithm :
- Keep the sum of the elements encountered thus far in a variable (say sum).
If the current sum is zero, we discovered a subarray beginning at index 0 and ending at index current index. - Check to see if the current sum is in the hash table.
- If the current sum already exists in the hash table, it means that it was the sum of some sub-array elements arr[0]…arr[i], and now the same sum is obtained for the current sub-array arr[0]…arr[j], implying that the sum of the sub-array arr[i+1]…arr[j] must be 0.
- Insert the current total into the hash table.
Run
#include <bits/stdc++.h> using namespace std; vector< pair<int, int> > findSubArrays(int arr[], int n) { // create an empty map unordered_map<int, vector<int> > map; vector <pair<int, int>> out; // Maintains sum of elements so far int sum = 0; for (int i = 0; i < n; i++) { // add current element to sum sum += arr[i]; // if sum is 0, we found a subarray starting // from index 0 and ending at index i if (sum == 0) out.push_back(make_pair(0, i)); if (map.find(sum) != map.end()) { // map[sum] stores starting index of all subarrays vector<int> vc = map[sum]; for (auto it = vc.begin(); it != vc.end(); it++) out.push_back(make_pair(*it + 1, i)); } // Important - no else map[sum].push_back(i); } // return output vector return out; } // Utility function to print all subarrays with sum 0 void print(vector<pair<int, int>> out) { for (auto it = out.begin(); it != out.end(); it++) cout << "Subarray found from Index " << it->first << " to " << it->second << endl; } // Driver code int main() { int arr[] = {6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7}; int n = sizeof(arr)/sizeof(arr[0]); vector<pair<int, int> > out = findSubArrays(arr, n); if (out.size() == 0) cout << "No subarray exists"; else print(out); return 0; }
Output
Subarray found from Index 2 to 4
Subarray found from Index 2 to 6
Subarray found from Index 5 to 6
Subarray found from Index 6 to 9
Subarray found from Index 0 to 10
Note:-
Time Complexity: O(N)
Auxiliary Space: O(N)
Login/Signup to comment