## Zero-Sum Sub-Arrays

### October 13, 2017

There is an obvious O(n2) algorithm, but this problem is similar to the well-known maximum sum subsequence problem, and admits a similar linear solution:

```(define (count xs)
(let ((counts (make-eq-hashtable))
(sum 0) (result 0))
(do ((xs xs (cdr xs))) ((null? xs) result)
(set! sum (+ sum (car xs)))
(when (hashtable-contains? counts sum)
(set! result (+ result (hashtable-ref counts sum 0))))

Our solution keeps a running sum as it scans the array, counting the number of times the sum has been seen previously in the `counts` hashtable. Each time a sum is the same as one previously found, we have found a zero-sum sub-array. Here’s an example:

```> (count '(-1 1 -1 1))
4```

You can run the program at https://ideone.com/hZ0Dag.

Pages: 1 2

### 6 Responses to “Zero-Sum Sub-Arrays”

1. nobody said

Please consider the input ‘(-1 1).

2. programmingpraxis said

Bah! Humbug.

3. V said

Solution in Ruby

```
def zero_sum_sub_arrays(xs)
return 0 if xs.size < 2

(2..xs.size)
.flat_map { |n| xs.each_cons(n).to_a }
.select { |xs| xs.sum == 0 }
.size
end

# Test

5.times do |n|
[1, -1].repeated_permutation(n).map do |input|
puts "#{input} -> #{zero_sum_sub_arrays(input)}"
end
end

```

produces:

```
[] -> 0
 -> 0
[-1] -> 0
[1, 1] -> 0
[1, -1] -> 1
[-1, 1] -> 1
[-1, -1] -> 0
[1, 1, 1] -> 0
[1, 1, -1] -> 1
[1, -1, 1] -> 2
[1, -1, -1] -> 1
[-1, 1, 1] -> 1
[-1, 1, -1] -> 2
[-1, -1, 1] -> 1
[-1, -1, -1] -> 0
[1, 1, 1, 1] -> 0
[1, 1, 1, -1] -> 1
[1, 1, -1, 1] -> 2
[1, 1, -1, -1] -> 2
[1, -1, 1, 1] -> 2
[1, -1, 1, -1] -> 4
[1, -1, -1, 1] -> 3
[1, -1, -1, -1] -> 1
[-1, 1, 1, 1] -> 1
[-1, 1, 1, -1] -> 3
[-1, 1, -1, 1] -> 4
[-1, 1, -1, -1] -> 2
[-1, -1, 1, 1] -> 2
[-1, -1, 1, -1] -> 2
[-1, -1, -1, 1] -> 1
[-1, -1, -1, -1] -> 0

```
4. Paul said

In Python.

```def number_of_pairs(n): return n * (n - 1) // 2

def zerosum(arr):
C = Counter(accumulate(+arr))
return sum(number_of_pairs(C[c]) for c in C)
```
5. Daniel said

Here’s a solution in C++11.

```#include <stdio.h>
#include <unordered_map>
#include <vector>

int zero_sum_count(std::vector<int>& vec) {
int count = 0;
int running_sum = 0;
std::unordered_map<int, int> lookup;
lookup = 1;
for (int value : vec) {
running_sum += value;
auto search = lookup.find(running_sum);
if (search == lookup.end()) {
lookup[running_sum] = 1;
} else {
count += search->second;
lookup[running_sum] += 1;
}
}
return count;
}

int main(int argc, char* argv[]) {
std::vector<int> vec = {-1, 1, -1, 1};
int count = zero_sum_count(vec);
printf("count: %d\n", count);
}
```

Output:

```\$ g++ -std=c++11 -o zero_sum_count zero_sum_count.cpp
\$ ./zero_sum_count
```
```count: 4
```
6. Sarthak Gupta said

Here’s a solution in Python3-

c = 0
l = [1, -1, 1, -1, -1, 1]
for i in range(len(l)):
for j in range(i+1,len(l)):
l1 = l[i:j+1]
if sum(l1) == 0:
print(l1)
c += 1
print(‘Total number of sub-arrays-‘, c)

Here’s the output-

[1, -1]
[1, -1, 1, -1]
[1, -1, 1, -1, -1, 1]
[-1, 1]
[1, -1]
[1, -1, -1, 1]
[-1, 1]
Total number of sub-arrays- 7