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