Programming Praxis

Zero-Sum Sub-Arrays

October 13, 2017 9:00 AM

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.

Posted by programmingpraxis

Categories: Exercises

Tags:

« Older Newer »

6 Responses to “Zero-Sum Sub-Arrays”

Please consider the input ‘(-1 1).

By nobody on October 13, 2017 at 7:02 PM
Bah! Humbug.

By programmingpraxis on October 13, 2017 at 7:05 PM

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
[1] -> 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

By V on October 14, 2017 at 3:54 AM

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)

By Paul on October 15, 2017 at 3:36 PM

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:

$ g++ -std=c++11 -o zero_sum_count zero_sum_count.cpp
$ ./zero_sum_count

count: 4

By Daniel on October 17, 2017 at 10:18 PM

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

By Sarthak Gupta on October 21, 2017 at 7:51 AM

Mobile Site | Full Site

Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.

Programming Praxis

Zero-Sum Sub-Arrays

Share this:

Related

6 Responses to “Zero-Sum Sub-Arrays”

Leave a Reply