## Zero-Sum Sub-Arrays

### October 13, 2017

There is an obvious O(*n*^{2}) 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)))) (hashtable-update! counts sum add1 1))))

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.

Advertisements

Pages: 1 2

Please consider the input ‘(-1 1).

Bah! Humbug.

Solution in Ruby

produces:

In Python.

Here’s a solution in C++11.

Output:

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