FastPrep
Problem · Array

Count Zero-Sum Fragments

Learn this problem
● MediumTesla logoTeslaOA

Problem statement

Write a function solution that, given an array A consisting of N integers, returns the number of fragments of A whose sum equals 0 (that is, pairs (P, Q) such that P <= Q and the sum A[P] + A[P+1] + ... + A[Q] is 0). The function should return -1 if this number exceeds 1,000,000,000.

The source also states: given A = [0, 0, ..., 0] of length 100,000, the function should return -1.

Function

solution(A: int[]) → int

Examples

Example 1

A = [2, -2, 3, 0, 4, -7]return = 4
Example 1 illustration

The zero-sum fragments shown in the source picture are:

  • [2, -2]
  • [0]
  • [3, 0, 4, -7]
  • [2, -2, 3, 0, 4, -7]

Constraints

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..100,000].
  • Each element of array A is an integer within the range [-10,000..10,000].

More Tesla problems

drafts saved locally
public int solution(int[] A) {
  // write your code here
}
A[2, -2, 3, 0, 4, -7]
expected4
checking account