Given an array and integer m, check how many unique contiguous subsets exist in the array such that each subset has m odd numbers.
Ex1: [2,5,6,9] m=1
[2,5], [5,6], [2,5,6],[5],[6,9],[9] are the possible subsets with m=1 odd numbers.
Result: 6
Ex2: [2,5,6,9] m=2
[2,5,6,9] and [5,6,9]
Result:2
What is better than a O(n2) solution. Can it be done with backtracking(is it needed)?
There’s an O(n) combinatorial solution which doesn’t need backtracking, but definitely needs pregen and sliding window technique
You can do it in O(N),Take another array A[]. Starting from the first position, keep track of number of odd numbers seen so far, store it in some variable ‘cnt’, and increment A[cnt], A[i] will contain the number of prefixes of the array with ‘i’ odd numbers, increment the answer by A[cnt-m] at every position if cnt>=m. Let me know (comment) if something is not clear.
What we’re doing here is, at every position ‘i’ in the array, we are counting the number of subarrays ending at ‘i’ and having ‘m’ odd numbers. Suppose that you want to know how many odd numbers are there in some range [L,R], your answer will be number of odd numbers in [0,R] - number of odd numbers in [0,L-1]. In the method that I mentioned, by the time you reach position ‘i’, you the variable cnt will be equal to the number of odd numbers in the range [0,i], so you need to find the number of previous positions that contain some ‘x’ odd numbers, so that if you take the subarray from that position to ‘i’, the resulting subarray will contain ‘m’ odd numbers, ie., cnt-x=m, x=cnt-m and we get that count from the other array that we are maintaining.
Eg. {2,5,6,9}, m=2
Suppose that you follow the method that I mentioned, by the time you reach the last position, the values stored in all variables will be: ans=0, cnt=2, A[0]=1, A[1]=2, A[2]=1 here, A[i] will contain the number of prefixes of the array that contain ‘i’ odd numbers, A[0]=1 because the prefix [2] has 0 odd numbers. A[1]=2 because, the prefixes [2,5] and [2,5,6] have 1 odd number and, similarly, A[2]=1. There are 2 odd numbers from the start of this array to the last position, so if there are any parts at the beginning that have 0 odd numbers in them, you can remove that part and the remaining part will have 2-0=2 odd numbers.
can you please explain/walkthrough how the algo would work for the Ex2 in the qs? THanks!
Here is my approach, almost same as @hemanth_1 logic
1.Save all the odd number as 1 and even as 0 in an array at the same index as given array.
2.Create a new array which stores the prefix sum of the above-created array.
3.Now you have two option: Either use two pointer technique to count the number of contiguous subarrays or use array to declare the output.
Here is the code:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int sum=0;
int n,k,ans=0;
cin>>n>>k;
int save[1000010],odd[n],a[n];
memset(save,0,sizeof(save));
save[0]++;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]%2==0)
odd[i] = 0;
else
odd[i] = 1;
sum +=odd[i];
if(sum >= k)
ans +=save[sum-k];
save[sum]++;
}
cout<<ans<<endl;
return 0;
}