Non-zero Segments

[rohitkumar9710]

Enter your question -

Kolya got an integer array a1,a2,…,an. The array can contain both positive and negative integers, but Kolya doesn't like 0, so the array doesn't contain any zeros.

Kolya doesn't like that the sum of some subsegments of his array can be 0. The subsegment is some consecutive segment of elements of the array.

You have to help Kolya and change his array in such a way that it doesn't contain any subsegments with the sum 0. To reach this goal, you can insert any integers between any pair of adjacent elements of the array (integers can be really any: positive, negative, 0, any by absolute value, even such a huge that they can't be represented in most standard programming languages).

Your task is to find the minimum number of integers you have to insert into Kolya's array in such a way that the resulting array doesn't contain any subsegments with the sum 0.

Test Case 1: Input: 4 1 -5 3 2 Output: 1

Explanation: Consider the first example. There is only one subsegment with the sum 0. It starts in the second element and ends in the fourth element. It's enough to insert one element so the array doesn't contain any subsegments with the sum equal to zero. For example, it is possible to insert the integer 1 between second and third elements of the array.

Enter link to the question(if question belongs to any online platform) -

https://codeforces.com/contest/1426/problem/D

Tags for the question(eg - Array, Basic, Stack, etc.) -

algorithm, greedy, rating: 1500

[rohitkumar9710]

@SarthakKeshari Kindly assign this issue to me.

[SarthakKeshari]

@rohitkumar9710, Kindly add your solution to "codeforces" folder. Deadline - 13/10/2021