Given that the array is picking up the number of auxiliary arrays with m odd numbers?

Question

Input example: 1 2 3 4 5 (array elements) m = 1 (Odd numbers) Output example: 8 . Subarrays are [ [1] , [1,2] , [2,3] , [2,3,4] , [3] , [3,4] , [4,5] , [5] ]

Here is my implementation. In the worst case, this will take O (n + n ^ 2). Are there 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, create an array of the lengths of the spaces between the odd numbers, counting both ends as implicit odd numbers. In this case, this array is g = [0,1,1,0] . Then we sum (g[i]+1)*(g[i+m]+1) because this means how many subarrays start with or not earlier than i'th odd and end on or immediately after i+m ' th odd.

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

Answer 2

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

However, for this you need an array sum [], in which the i-th position shows the number of odd numbers in the interval [0, i]. This can be precomputed in O (n) using one for the loop.

Now you use it as 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; }