Count Distinct Subarrays With At Most K Odd Elements
You are given an array “A” 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 A = [3,2,3], and K = 1 then there are 4 subarrays with at most K odd elements: [3], [3,2], [2,3],[2]

Input format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow. The first line of each test case contains single space-separated two integers N and K. The second line of each test case contains N space-separated integers, denoting the elements of array A.

Output format :

For each test case, print the number of distinct subarrays with at most K odd elements.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1

Question

Count Distinct Subarrays With At Most K Odd Elements

You are given an array “A” 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 A = [3,2,3], and K = 1 
then there are 4 subarrays with at most K odd elements:
 [3], [3,2], [2,3],[2]

Input format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

Then the T test cases follow.

The first line of each test case contains single space-separated two integers N and K.

The second line of each test case contains N space-separated integers, denoting the elements of array A.

Output format :

For each test case, print the number of distinct subarrays with at most K odd elements.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10    
1 <= N <= 100
0 <= K <= N
1 <= A[i] <= 10 ^ 9

Where A[i] denotes the 'ith' element of A.

Time Limit: 1sec

Accepted Answer

Hashing Approach

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

Space Complexity: O(n^2)Explanation:

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

In the worst case, when we have all even, 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).

Time Complexity: O(n^3)Explanation:

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

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

Note :

Example :

Input format :

Output format :

Note :

Constraints :

Top Jio Platforms Graduate Engineer Trainee (Get) interview questions & answers

Popular interview questions of Graduate Engineer Trainee (Get)

Top HR questions asked in Jio Platforms Graduate Engineer Trainee (Get)