## Zero-Sum Sub-Arrays

### October 13, 2017

This interesting little question comes from Career Cup:

Given an array that contains only the elements -1 and 1, find the number of sub-arrays with a sum of zero. For instance, given the array [-1, 1, -1, 1], there are four sub-arrays that sum to zero: [-1, 1], [1, -1], [-1, 1] and [-1, 1, -1, 1].

Your task is to count the sub-arrays of a -1/1 array that sum to zero. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

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