Find the number of continuous sequence of numbers such that their sum is zero.
For example if the sequence is- 5, 2, -2, 5, -5, 9
There are 3 such sequences
2, -2= (2+-2)=0
5, -5=(5+-5)=0
2, -2, 5, -5=(2+-2+5+-5)=0
so ans is 3;
Problem link: https://www.spoj.com/problems/CRAN02/\
Hints:
At first we need to comulative sum of the array then sort the sum array and find a pair of same digit.then calculate n*(n+1)/2 and add with result;
Example: 5,2,-2,5,-5,9
Commulative sum array={5,7,5,10,5,14} and add 0 in position 0
So the array is={0,5,7,5,10,5,14} now sort the array.
So the array is={0,5,5,5,7,10,14}
the find pair of same digit 1st pair is 5,5 and 2nd is 5,5 so 2 pairs and (2*(2+1))/2; so the result is (2*3)/2=3
Source Code:
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
unsigned long long int a[10000100]= {0},b[10000100]= {0},c[10000100]= {0};
int main()
{
unsigned long long int i,j,k,l=0,n,m,sum=0,r,sum1=0,p,t;
scanf("%llu",&n);
for(i=0; i<n; i++)
{
scanf("%llu",&m);
sum=0;
sum1=0;
for(j=0; j<m; j++)
{
scanf("%llu",&a[j]);
sum=sum+a[j];
b[j+1]=sum;
}
sort(b,b+m+1);
l=0;
for(p=0; p<m; p++)
{
if(b[p]==b[p+1])
{
c[l]++;
}
else
{
l++;
}
}
for(r=0; r<=l; r++)
{
sum1=sum1+(c[r]*(c[r]+1)/2);
}
memset(c,0,sizeof(c));
printf("%llu\n",sum1);
}
return 0;
}
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন