O(n) cpp Solution without hashing


#1

bool odd(int a)
{
return a % 2 == 1;
}

int Solution::solve(vector &A, int B) {

int n = A.size();
int cnt = 0,l=0,r=0;
long long i = 0,j = 0;
long long ans = 0;

if(B == 0)
{
    while(i<n)
    {
        while(i < n && !odd(A[i]))
            i++,j++;
        ans += ((j)*(j+1))/2;
        j = 0;
        i++;
    }
    return ans;
}
while(j < n)
{
    while(j < n && cnt < B)
        if(odd(A[j++]))
            cnt++;
    if(cnt < B)
        return 0;
    while(!odd(A[i]))
        i++, l++;
    while(j < n && !odd(A[j]))
        j++, r++;
    ans += (l+1)*(r+1);
    l = 0;
    r = 0;
    i++;
    cnt--;
}
return ans;

}


#2

Much Simpler than yours
int countSubarrays(vector a, int m) {
int count = 0, n = a.size();
int prefix[n] = {0};
int odd = 0;
for (int i = 0; i < n; i++){
prefix[odd]++;
if (a[i] & 1)
odd++;
if (odd >= m)
count += prefix[odd - m];
}
return count;
}