Skip to main content

D_ Count Interval-AtCoder Beginner Contest 233 (C++ Code and Explanation)

 D-Count Interval AtCoder Beginner Contest 233 


Problem- https://atcoder.jp/contests/abc233/tasks/abc233_d

Approach-

Since, negative numbers are also allowed, we cannot use the traditional method of sliding window here. So, we will use unordered_map to store the subarray sum we have encountered till now and if the difference of current sum is already present in our map then this means that the subarray after the previous one also has sum equals k.
For example k is 7 and array is {3, 4, 7}, then for index 0 and 1 map stores 7 as a subarray sum and then as we encounter index 2, current sum is 14. Now current sum-k is 7 and it is already present, this signifies that the current subarray sum is also k.
Below is the code matching with the exact explanation above.

Code-

long long s=0, ans=0;
unordered_map<long long, long long>m;
for(long long i=0;i<n;i++)
{
    s+=a[i];
    if(s==k)
        ans++;
    else if(m.find(s-k)!=m.end());
        ans+=m[s-k];
    m[s]++;
}
cout<< ans;


Disclaimer- Everything is published after the actual contest gets over.