O(n) cpp solution


#1

We can assigned the odd value to 1 and even value to 0. Then the problem breaks down to finding the number of subarrays whose Sum equal to B.
int Solution::solve(vector &A, int B) {
unordered_map<int,int> ump;

int n = A.size();
int indx=0;
int ans=0;
for(int i=0;i<n;i++){
    if(A[i]%2)
        A[i]=1;
    else
        A[i]=0;
        
}
//Problem break down to number of subarray whose Sum equal to B.
ump[0]=1;
int sum=0;
for(int i=0;i<n;i++){
    
    sum +=A[i];
    
    if(ump.find(sum-B) != ump.end()){
        ans += ump[sum-B];
        // cout<<ans<<" ";
    }
        
        ump[sum]++;
}

return ans;

}


#2

what is the logic behind using below code plzz explain

for(int i=0;i<n;i++){
    
    sum +=A[i];
    
    if(ump.find(sum-B) != ump.end()){
        ans += ump[sum-B];
        // cout<<ans<<" ";
    }
        
        ump[sum]++;
}

return ans;

}


#3

This is the code for finding number of subarrays whose sum is equal to B.


#5

Dude Can you please explain why you have used ump[0]=1???


#6

Awesome solution dude!


#7

Thank you soo much bro!.


#8

Please explain the for loop logic someone please.


#9

Its little bit confusing.its mainly finding subarrays with k sum.you can use this approach as it is easy to understand and no need to initialize map[0]=1;
unordered_map<int,int>mp;
int ans=0,sum=0;
for(int i=0;i<A.size();i++)
{
sum+=A[i];
if(sum==B)ans++;
if(mp.find(sum-B)!=mp.end())ans+=mp[sum-B];
mp[sum]++;
}
return ans;