CODEWITHSUNDEEP
c++arraysalgorithm
Sanjeevkumar M
Sanjeevkumar M

Reputation: 101

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

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;
}

Upvotes: 6

Views: 4752

Answers (2)

btilly
btilly

Reputation: 46408

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).

Upvotes: 8

Zoomba
Zoomba

Reputation: 1806

You can easily get O(n log n). A simple improvement for your code is that in your inner loop (on j), instead of going one by one and counting you do a binary search on the interval [i, n] to find the first position that results in m odd numbers, and the first position that results in m+1 odd numbers; then subtract them.

However, to do this you need to have a sum[] array in which the ith position shows the number of odd numbers in interval [0, i]. This can be precomputed in O(n) with one for loop.

Now you use it like this in your binary search:

for(int i = 0; i < n; i++){
    int lo = i;
    int hi = n;

    while(lo < hi){
        int mid = (lo + hi)/2;
        int count = sum[mid];
        if(i > 0) count -= sum[i - 1];

        //count shows number of odd in the interval [i, mid]
        if(mid >= m){
            hi = mid;
        } 
        else{
            lo = mid + 1;
        }
    }

    int first_with_m = lo;

    //do another binary search to find first_with_m_plus_one

    answer += first_with_m_plus_one - first_with_m;
}

Upvotes: 2

Related Questions