# Zero sum sub-array

July 18, 2011 3 Comments

Question: There is an array consisting of postive and negative integers. find the subarray whose sum is 0.

Solution:

#include<ext/hash_map> #include<iostream> #include<vector> using namespace __gnu_cxx; using namespace std; int main() { int n; cin >> n; int prefix_sum = 0; hash_map<int, int> find_subarray; int start_index = -1, end_index = -1; for (int i = 0, t = -1; i < n; ++i) { cin >> t; if (!t) { start_index = i; end_index = i; break; } prefix_sum += t; if (!prefix_sum) { start_index = 0; end_index = i; break; } if (find_subarray.find(prefix_sum) == find_subarray.end()) { find_subarray[prefix_sum] = i; } else { start_index = find_subarray[prefix_sum] + 1; end_index = i; break; } } if (start_index != -1) { cout << "Zero sum subarray found. Start index : " << start_index << ". End Index: " << end_index << "\n"; } return 0; }

Advertisements

Still N square Solution. NlogN solution is more obvious.

Isn’t this NP complete?

http://en.wikipedia.org/wiki/Subset_sum_problem

Correct. Hence the solution is exponential in n.