Find number of continuous subarray having sum zero

Question

You have given a array and You have to give number of continuous subarray which the sum is zero.

example:
1)  0 ,1,-1,0 => 6 {{0},{1,-1},{0,1,-1},{1,-1,0},{0}};
2)  5, 2, -2, 5 ,-5, 9 => 3.

With O(n^2) it can be done.I am trying to find the solution below this complexity.

Answer 1

https://www.techiedelight.com/find-sub-array-with-0-sum/

This would be an exact solution.

# Utility function to insert <key, value> into the dict
def insert(dict, key, value):
 
    # if the key is seen for the first time, initialize the list
    dict.setdefault(key, []).append(value)
 
 
# Function to print all sub-lists with 0 sum present
# in the given list
def printallSublists(A):
 
    # create an empty -dict to store ending index of all
    # sub-lists having same sum
    dict = {}
 
    # insert (0, -1) pair into the dict to handle the case when
    # sub-list with 0 sum starts from index 0
    insert(dict, 0, -1)
 
    result = 0
    sum = 0
 
    # traverse the given list
    for i in range(len(A)):
 
        # sum of elements so far
        sum += A[i]
 
        # if sum is seen before, there exists at-least one
        # sub-list with 0 sum
        if sum in dict:
 
            list = dict.get(sum)
            result += len(list)
            # find all sub-lists with same sum
            for value in list:
                print("Sublist is", (value + 1, i))
 
        # insert (sum so far, current index) pair into the -dict
        insert(dict, sum, i)

    print("length :", result)

if __name__ == '__main__':
 
    A = [0, 1, 2, -3, 0, 2, -2]
 
    printallSublists(A)

Answer 2

C# version of @stgatilov answer https://stackoverflow.com/a/31489960/3087417 with readable variables:

        int[] sums = new int[arr.Count() + 1];
        for (int i = 0; i < arr.Count(); i++)
            sums[i + 1] = sums[i] + arr[i];

        int numberOfFragments = 0;
        Dictionary<int, int> sumToNumberOfRepetitions = new Dictionary<int, int>();

        foreach (int item in sums)
        {
            if (sumToNumberOfRepetitions.ContainsKey(item))
                numberOfFragments += sumToNumberOfRepetitions[item];
            else
                sumToNumberOfRepetitions.Add(item, 0);

            sumToNumberOfRepetitions[item]++;
        }

        return numberOfFragments;

If you want to have sum not only zero but any number k, here is the hint:

            int numToFind = currentSum - k;
            if (sumToNumberOfRepetitions.ContainsKey(numToFind))
                numberOfFragments += sumToNumberOfRepetitions[numToFind];

Answer 3

This can be solved in linear time by keeping a hash table of sums reached during the array traversal. The number of subsets can then be directly calculated from the counts of revisited sums.

Haskell version:

import qualified Data.Map as M
import Data.List (foldl')

f = foldl' (\b a -> b + div (a * (a + 1)) 2) 0 . M.elems . snd
  . foldl' (\(s,m) x -> let s' = s + x in case M.lookup s' m of 
                          Nothing   -> (s',M.insert s' 0 m)
                          otherwise -> (s',M.adjust (+1) s' m)) (0,M.fromList[(0,0)])

Output:

*Main> f [0,1,-1,0]
6

*Main> f [5,2,-2,5,-5,9]
3

*Main> f [0,0,0,0]
10

*Main> f [0,1,0,0]
4

*Main> f [0,1,0,0,2,3,-3]
5

*Main> f [0,1,-1,0,0,2,3,-3]
11                              

Answer 4

Consider S[0..N] - prefix sums of your array, i.e. S[k] = A[0] + A[1] + ... + A[k-1] for k from 0 to N.

Now sum of elements from L to R-1 is zero if and only if S[R] = S[L]. It means that you have to find number of indices 0 <= L < R <= N such that S[L] = S[R].

This problem can be solved with a hash table. Iterate over elements of S[] while maintaining for each value X number of times it was met in the already processed part of S[]. These counts should be stored in a hash map, where the number X is a key, and the count H[X] is the value. When you meet a new elements S[i], add H[S[i]] to your answer (these account for substrings ending with (i-1)-st element), then increment H[S[i]] by one.

Note that if sum of absolute values of array elements is small, you can use a simple array instead of hash table. The complexity is linear on average.

Here is the code:

long long CountZeroSubstrings(vector<int> A) {
    int n = A.size();

    vector<long long> S(n+1, 0);
    for (int i = 0; i < n; i++)
        S[i+1] = S[i] + A[i];

    long long answer = 0;
    unordered_map<long long, int> H;
    for (int i = 0; i <= n; i++) {
        if (H.count(S[i]))
            answer += H[S[i]];
        H[S[i]]++;      
    }

    return answer;
}

Answer 5

I feel it can be solved using DP: Let the state be : DP[i][j] represents the number of ways j can be formed using all the subarrays ending at i!

Transitions:

for every element in the initial step ,

Increase the number of ways to form Element[i] using i elements by 1 i.e. using the subarray of length 1 starting from i and ending with i i.e

DP[i][Element[i]]++;

then for every j in Range [ -Mod(highest Magnitude of any element ) , Mod(highest Magnitude of any element) ]

DP[i][j]+=DP[i-1][j-Element[i]];

Then your answer will be the sum of all the DP[i][0] (Number of ways to form 0 using subarrays ending at i ) where i varies from 1 to Number of elements

Complexity is O(MOD highest magnitude of any element * Number of Elements)

Answer 6

I don't know what the complexity of my suggestion would be but i have an idea :)
What you can do is try to reduce element from main array which are not able to contribute for you solution suppose elements are -10, 5, 2, -2, 5,7 ,-5, 9,11,19
so you can see that -10,9,11 and 19 are element
that are never gone be useful to make sum 0 in your case
so try to remove -10,9,11, and 19 from your main array to do this what you can do is

1) create two sub array from your main array  
`positive {5,7,2,9,11,19}` and `negative {-10,-2,-5}`   
2) remove element from positive array which does not satisfy condition
   condition -> value should be construct from negative arrays element  
   or sum of  its elements  
   ie.   
       5 = -5 //so keep it //don't consider the sign  
       7 = (-5 + -2 ) // keep  
       2 = -2 // keep
       9 // cannot be construct using -10,-2,-5  
       same for all 11 and 19
3) remove element form negative array which does not satisfy condition
      condition -> value should be construct from positive arrays element  
       or sum of  its elements   
  i.e. -10 // cannot be construct so discard  
       -2 = 2 // keep  
       -5 = 5 // keep 

so finally you got an array which contains -2,-5,5,7,2 create all possible sub array form it and check for sum = 0
(Note if your input array contains 0 add all 0's in final array)