Krypton31's blog

By Krypton31, history, 2 months ago,

Can you please help me see my mistake, in Subarray Sums || It gives WA for 2 cases.

int main(){
FastIO;
int n;
ll x;
cin>>n>>x;
ll a[n];
ll prefix[n];
for(int i=0;i<n;i++){
cin>>a[i];
prefix[i] = a[i];
if(i>0) prefix[i]+=prefix[i-1];
}
map<ll,ll>cache;
int cnt =0;
for(int i =0;i<n;i++){
cache[prefix[i]]+=1;
if(prefix[i]==x and cache[0]==0) cnt+=1;
else cnt+=cache[prefix[i]-x];
}
cout<<cnt;
return 0;
}


• +1

 » 2 months ago, # |   0 I modified this part of the code and got accepted. mapcache; cache[0] = 1; int cnt = 0; for(int i=0;i
•  » » 2 months ago, # ^ |   0 Hey Thanks, can you please elaborate what was my mistake, like any edge cases also can you put simply why you did what you did?
•  » » 2 months ago, # ^ |   0 also why — sign tho, what difference does it make and I get that you added 0 for prefix(i)=x so what is wrong with the if condition of mine, plz help?
•  » » » 2 months ago, # ^ |   +1 Your code will fail for testcases like these 5 100 100 100 100 100 100 because cache[0] = 0 initially so everytime after the first 100 we will add 1 to the ans due to if condition. So initially cache[0] should be made 1 and if condition should be removed. cache[prefix[i]]+=1; should be done at the end of the loop so as to manage testcases like 5 0 0 0 0 0 0 and cnt should be made ll. int main(){ int n; ll x; cin>>n>>x; ll a[n]; ll prefix[n]; for(int i=0;i>a[i]; prefix[i] = a[i]; if(i>0) prefix[i]+=prefix[i-1]; } mapcache; cache[0] = 1; ll cnt =0; for(int i =0;i
•  » » » » 2 months ago, # ^ |   0 Ah yes, Thank you sir, I get it.