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

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
    [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
    
    
  4. Paul said

    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)
    
  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[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
    
  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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: