New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Even Odd Pulse

Contributed by

Sachin_f78a

Last Updated: 23 Feb, 2023

Medium

0/80

Avg time to solve 15 mins

Success Rate 80 %

0 upvotes

Problem Statement

You are given an array 'A' of size 'N' and an integer 'K'.

The 'Pulse' of a subarray of 'A' is defined as the product of the number of even elements and the number of odd elements in that subarray.

Return the minimum possible length of a subarray having 'Pulse' greater than or equal to 'K'. If there does not exist any subarray having 'Pulse' greater than or equal to 'K', then return -1.

Note : Assume 0-based indexing.

A subarray is any contiguous part of an array.

For example:

Let 'N' = 5, 'K' = 4, 'A' = [2, 2, 2, 1, 1].
There exist only two subarrays, 'A[0…4]' and 'A[1…4]' having 'Pulse' greater than or equal to 'K'. 
'Pulse' of 'A[0…4]' is 6 and the length is 5.
'Pulse' of 'A[1…4]' is 4 and the length is 4.
 Since we have to minimize the length, therefore 4 will be our answer.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:-

The first line contains an integer 'T', which denotes the number of test cases.
For every test case:-
The first line contains two space-separated integers 'N' and 'K', denoting the number of elements in the array 'A' and the minimum required 'Pulse' of the subarray respectively.
The second line contains 'N' space-separated integers, denoting the elements of the array 'A'.

Output Format:-

Return the minimum possible length of a subarray having 'Pulse' greater than or equal to 'K'.      
If there does not exist any subarray having 'Pulse' greater than or equal to 'K', then return -1.

Note:-

You don’t need to print anything. Just implement the given function.

Constraints:-

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

The sum of 'N' over all test cases does not exceed 10^5.    

Time Limit: 1 sec

Sample Input 1:-

2
6 6
2 1 2 3 4 3
1 2
1

Sample Output 1:-

5
-1

Explanation of sample input 1:-

First test case:-
There exist only three subarrays, 'A[0…4]',  'A[1…5]' and 'A[ 0…5]' having 'Pulse' greater than or equal to 'K'. 
'Pulse' of 'A[0…4]' is 6 and the length is 5.
'Pulse' of 'A[1…5]' is 6 and the length is 5.
'Pulse' of 'A[0…5]' is 9 and the length is 6.
Since we have to minimize the length, therefore 5 will be our answer.


Second test case:-
There does not exist any subarray having 'Pulse' greater than or equal to 'K'.

Sample Input 2:-

Sample Output 2:-

2
3

Auto

Console