Hello ,
problem : Problem - C - Codeforces
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