Distinct Subarrays with at most k odd elements II

Hard
0/120
Average time to solve is 40m
profile
Contributed by
4 upvotes
Asked in companies
ShareChatFlipkart limited

Problem statement

You are given an array “ARR” of N integers. Your task is to find the total number of distinct subarrays of A having at most K odd elements.

Note: 
Two subarrays are distinct when they have at least one different element.
Example: 
If ARR = [3,2,3], and K = 1 
then there are 4 subarrays with at most K odd elements:
 [3], [3,2], [2,3],[2]
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

The first line of each test contains single space-separated two integers N and K.
The second line of each test contains N space-separated integers, denoting the elements of array ARR.
Output format : 
For each test case, print the number of distinct subarrays with at most K odd elements.
Constraints : 
1 <= T <= 10    
1 <= N <= 3000
1 <= K <= N
1 <= ARR[i] <= 10^9

Time Limit: 1sec
Note: 
 You do not need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1 :
2 
3 1
2 1 1
3 3
1 1 1
Sample Output 1 :
3
3
Explanation for sample input 1 :
For the first test case, the following are 3 valid subarrays:

[2,1], [1], [2]

For the second test case, following are 3 valid subarrays :

[1], [1,1] and [1,1,1]

Sample Input 2 :
2
3 2
1 3 1
3 3
1 5 3
Sample Output 2 :
4
6
Hint

Think of a solution to check each subarray.

Approaches (3)
Brute Force

In this solution, we try to generate all subarrays and check if the subarray contains at most K odd elements or not. Also, we will build a HashSet of the subarray to check if any subarray is already in the HashSet or not. If the subarray contains at most K odd elements and it is not present in the HashSet then we will increment our answer by 1.


 

Steps: 

  • Declare a variable to store the count of distinct subarrays with at most K odd elements, say answer.
  • Create a HashSet to check whether we have included this subarray in our answer or not.
  • Run two nested loops to generate all subarrays.
  • If any subarray has a count of odd elements <= K and is not present in a HashSet then increment answer by 1 i.e., do answer += 1.
  • At last, we return the answer.
Time Complexity

O(N ^ 3), where N is the length of the given array.

In the worst case, generating all subarrays takes O(N^2) time, and checking if the subarray present in the HashSet takes O(N) time. Hence the overall complexity will be O(N ^ 3).

Space Complexity

O(N^2), where N is the length of the given array.

In the worst case, when we have all odd, and unique elements in the array then, there will be a total N^2 subarray which will be stored in HashSet. Hence the overall space complexity will be O(N^2).

Code Solution
(100% EXP penalty)
Distinct Subarrays with at most k odd elements II
Full screen
Console