CODEWITHSUNDEEP
arraysalgorithm
Ankit Kumar
Ankit Kumar

Reputation: 1281

Find all subsets of an array with sum 0

I'm given an array of size upto 10^5 (call it n) containing integers. I have to find number to pairs (i,j), i < j such that a_i+...+a_j = 0.

My attempt:

Clearly the algo should not take more than nlogn. I wrote an n^2 algo that goes as:

  1. For all i, find sum of all elements before it (sum[i][0]) and after it (sum[i][1]). This will take O(n) time.

  2. Call sum of all elements tSum.

  3. For any (i,j) I can find the required in sum in O(1) time using tSum - sum[j][1] - sum[i][0].

Since possible no of such (i,j) is of order n^2, it will take me O(n^2) time. I tried, but was unable to reduce it down to O(n) or O(nlogn). Please give me some hints on how this could be done. Thanks...

Upvotes: 0

Views: 291

Answers (3)

jferard
jferard

Reputation: 8190

Let S be the array:

S[i] = a_0 + ... + a_i-1

Then, 

S[j+1] - S[i] = a_j + ... + a_i

You want to find the pairs i < j having S[i] == S[j+1].

In O(n lg n): just sort S (on values, but keep the indices) and check for consecutives values that are identic.

In amortized O(n): create a hash map x -> [all i with S[i] == x] and output the combinations if there are two elements or more.

Upvotes: 3

hbejgel
hbejgel

Reputation: 4847

Instead of step 3, you can create a dictionary keyed by tSum - sum[j][1] and with value of j, you do this for all elements and go through the array again checking for the presence of sum[i][0] in the dictionary, if it is there you can output the pair i, j.

Upvotes: 1

Maras
Maras

Reputation: 982

You can do it in O(n log n) or even O(n).

Create empty set of pairs (number, number of its occurrences) S (BST - O(n log n), hash array - expected O(n))

For each i from 1 to n (where n is the length of the array):

  • Calculate prefix sum. (prefsum[i] = prefsum[i-1] + array[i]) Let's call it x.

  • Find number of x in a set S. Add it to the result (if you had previously a prefix sum with sum x, you can substract it from you current prefix sum and get a subarray with sum equal to 0)

  • Add/increase amount of x in S

Upvotes: 1

Related Questions