Menu Close

Calculate the number of non-empty good sub-arrays ….[Cprogm]FTC

Eugene likes working with arrays. And today he needs your help in solving one challenging task.

An array c is a sub-array of an array b if c can be obtained from b by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Let’s call a nonempty array good if for every nonempty sub-array of this array, sum of the elements of this sub-array is nonzero.
For example, array [−1, 2, −3] is good,
as all arrays [−1] , [−1, 2] , [−1, 2, −3] , [2] , [2, −3] , [−3] have nonzero sums of elements. However, array [−1, 2, −1, −3] isn’t good, as his sub-array [−1,2,−1] has sum of elements equal to 0.

Help Eugene to calculate the number of nonempty good sub-arrays of a given array a .

Input:
The first line of the input contains integer n — the length of array a .

The second line of the input contains n integers a1,a2,…,an a_1, a_2, a_n — the elements of a .

Output:
Output a single integer — the number of good subarrays of a.

sample input
3
1 2 -3

sample output
5

The following sub-arrays are good: [1], [1,2], [2], [2,−3], [−3]. However, the sub-array [1,2,−3] isn’t good, as its sub-array [1,2,−3] has a sum of elements equal to 0.

#include <stdio.h>
int main()
{
  int *ii;
  int i,j,n,count=0,sum=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&ii[i]);
  }
  for(i=0;i<n;i++){
    sum=0;
    for(j=i;j<n;j++){
      sum+=ii[j];
      if(sum!=0){count+=1;}
      else{break;}
    }
  }
printf("\n%d\n",count);
return 0;
}

INPUT_1:
2
1  -1

OUTPUT:
2


INPUT_2:
3
41  -41  41

OUTPUT:
3


INPUT_3:
3
2  3  -3

OUTPUT:
5


INPUT_4:
4
1  2  3  -5

OUTPUT:
9


ILLUSTRATION:

Executed using gcc Linux