Codeforces ER 93 -C

Hello ,
problem : https://codeforces.com/contest/1398/problem/C

To Find: Given Array find the number of subarray with sum same as length of subarray

solution :
It is similar to problem : finding subarray with sum K.
so, we first do : prefix sum for array
eg; arr[3,0,0 ,0,0, 5]
index -> prefixsum
1 -> 3
2 ->. 3
3 -> 3
4 ->. 3
5 ->. 3
6 -> 8

in the above example we see the we get subarray of sum 5 and length 5 (0,0,0,0,5)
so we see that if subarray. is (prefixsum-index)

for condition to satisfy we must make index = prefix sum --> x->x;
so, for we can make. 6->8 - (1->3). --> (5->5). we get subarray from 2-6 which satisfy our condition and the difference of (6-8) == (1-3)
so, we use a hashmap to store the count of diff(val),
ans for each count diff value. --we can form nC2 pairs
the map gives us the subarray of size >1

#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl “\n”;
//#pragma GCC optimize “trapv”
using namespace std;
typedef long long int ll;
int mx =1e6+100;
int main()
{
int T;
cin>>T;
while(T–)
{
int n;
cin>>n;
string s;
cin>>s;
map<ll,ll>mp;
ll sum=0;
ll ct=0;
for(int i=0;i<n;i++)
{
sum +=s[i]-‘0’;
if(sum==(i+1))ct++;
mp[sum-i]++;
}

   for(auto i:mp)
    {
        ct+=(i.second * (i.second-1))/2;
    }
    cout<<ct<<endl;
}
return 0;

}`

PS:If anything wrong in my approach please let me know

I think this line should not be there because here you are additionally adding the no. of subarrays that starts from i=0 . Also you are counting the subarrays starting from 0 when you are using range based for loop for map. And also in starting you should make value of mp[1]=1 as you are substracting the 0 based index system.

No, it is used to count during prefix sum and index form start(complete array) whereas the function is used to calculate the subarray