-1

Recently I encountered a question which says that we need to find the number of pairs in an array between(inclusive of both ends) which sum of elements is equal to 0. For eg : int[] arr = {1,-2,3,0,-2,2}. Then the pairs between which sum of elements is 0 are (3,5), (4,5), (0,4). So the ans = 3. Is there any way we can solve this in O(n) .

Anshul
  • 415
  • 4
  • 15
  • Use a hashmap.. – nice_dev Feb 08 '20 at 11:48
  • Ok , that was quick . But how ?. I recently started with some practise of ds/algo. Your help will really be appreciated with some pseudo code :) – Anshul Feb 08 '20 at 11:50
  • 1
    Does this answer your question? [Find all pairs of integers within an array which sum to a specified value](https://stackoverflow.com/questions/1494130/find-all-pairs-of-integers-within-an-array-which-sum-to-a-specified-value) – default locale Feb 08 '20 at 11:51
  • @Anshul Store all elements in map. Check if map has -A[i] value – nice_dev Feb 08 '20 at 12:00
  • Counting pairs can be O(n) however accumulating them cannot be O(n) – nice_dev Feb 08 '20 at 12:01
  • 2
    Your question is a little hard to parse. I think you want to count all the contiguous subarrays with zero sum, but commenters seem to think you want to count all pairs with zero sum. – Matt Timmermans Feb 08 '20 at 16:53
  • @MattTimmermans, yes you are right , I want to find all contiguous subarrays with 0 sum – Anshul Feb 09 '20 at 08:53
  • @Anshul Then see if this question helps: [Counting all contiguous sub-arrays given sum zero](https://stackoverflow.com/questions/26532723/counting-all-contiguous-sub-arrays-given-sum-zero) – default locale Feb 10 '20 at 03:18

1 Answers1

0

The trick you need for this one is to build an array of cumulative sums, so that sums[i] = sum of all arr[0] through arr[i].

Of course, if sums[i] == 0, then (0,i) is one of the pairs you're looking for, and you should count it.

For all the other ones, note that if the sum of arr[i] though arr[j] is zero, then sums[i-1] == sums[j].

So you just need to know how many matching pairs of values there are in sums.

Make a hash map from value->number that gives the frequency of each value in sums. Then, for each count m that's at least 2, you have m*(m-1)/2 pairs.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87