Given an array find the number of sub arrays with m odd numbers?

Question

Sample Input: 1 2 3 4 5 (array elements) m = 1 (Odd numbers) Sample output: 8. The subarrays are [[1], [1,2], [2,3], [2,3,4], [3], [3,4], [4,5], [5] ]

Here is my implementation.In the worst case, it would take O(n+n^2).Are there any ways to optimize this code?

int main() {
    int n, *a, count1=0, m, *dp;
    cin>>n;
    a = new int[n];
    dp =new int[n];

    for(int i=0; i<n; i++) {
        cin >> a[i];
    }

    cin >> m;

    for(int i=0; i<n; i++){
        if(a[i]%2==1) {
            count1++;
        }

        dp[i] =count1;
    }

    int prev;
    long count=0;

    for(int i=0; i<n; i++) {
        prev= i==0 ? 0:dp[i-1];
        for(int j=i; j<n; j++) {
            if((dp[j] - prev) == m){
                count++;
            }

            if(dp[j] - prev > m){
                break;
            }
        }
    }
    cout<<count;
}

Answer 1

This can be solved in O(n). First generate an array of the lengths of the gaps between odd numbers, counting both ends as implicit odd numbers. In this case that array is g = [0,1,1,0]. Then we sum (g[i]+1)*(g[i+m]+1) because that represents how many subarrays start at or just before the i'th odd, and end at or just after the i+m'th odd.

In this case we get 1*2 + 2*2 + 2*1 = 8.

Alternate explanation Think about the list of wanted subarrays. Each one starts somewhere, includes m odd numbers, then ends somewhere else. Let us divide them into groups based on which string of odd numbers they include. Each group contains the ith odd number for some i, and ends at the i+m-1'th odd number. The starting points are at every even number between the i-1th and ith odd numbers, and the ith odd number itself. That's the size of the gap before the ith odd number + 1. Or g(i)+1 in my calculation. Similarly the ending points are at the i+m-1th odd number, or at all the evens between that and the i+mth odd number. That's 1 more the size of the gap between the i+m-1th and i+mth odd numbers. Which is g(i+m)+1 in my calculation. The number in that group is therefore the number of starting points times the number of ending points. Which is (g(i)+1)*(g(i+m)+1). Add that over all starting points i and we have our answer.

There is one important detail that I glossed over. Which is that I am assuming that odd numbers are included, so 0 < m. If m = 0 then the calculation changes completely. The answer then turns out to be 1 + sum(g(i)*(g(i)-1)/2).