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.
Programming Praxis 
Please consider the input ‘(-1 1).
Bah! Humbug.
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 endproduces:
In Python.
def number_of_pairs(n): return n * (n - 1) // 2 def zerosum(arr): C = Counter(accumulate([0]+arr)) return sum(number_of_pairs(C[c]) for c in C)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[0] = 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:
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