Even Odd Pulse

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
1 upvote

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:-
2
2 1
1 2
4 2
1 1 2 1
Sample Output 2:-
2
3
Hint

Can we determine the 'Pulse' of all possible subarrays?

Approaches (2)
Brute force

Approach:-

 

Using a nested for-loop we can easily calculate the 'Pulse' of each subarray and then determine the subarray having minimum length and 'Pulse' greater than or equal to 'K'. If there does not exist any subarray having 'Pulse' greater than 'K' then we will return -1.  

           

 Algorithm:-

 

  • Initialize an integer variable 'minLength' = 'INT_MAX' to store the minimum possible length.
  • Iterate over elements of 'A' from 'i' = 0 to 'i' = 'N-1'.
    • Initialize integer variables 'evenCount' = 0 and 'oddCount' = 0, to store number of even elements and number of odd elements respectively.
    • Iterate over elements of 'A' from 'j' = i to 'j' = 'N-1'.
      • If 'A[j]' is odd, then increment oddCount.
      • Else increment 'evenCount'.
    • If 'evenCount * oddCount' is greater than or equal to 'K', then the current subarray's length can be our answer.
      • Update 'minLength' to 'min(minLength,j-i+1).
  • If 'minLength' is equal to 'INT_MAX', it means that there exists no subarray having 'Pulse' greater than or equal to 'K', therefore return -1.
  • Else return 'minLength' as the answer.
Time Complexity

O(N^2), where 'N' is the number of elements in 'A'.

 

Since we are checking for each and every subarray possible and the total number of subarrays are of the order of N^2. Therefore time complexity is O(N^2).

Space Complexity

O(1)

 

Since we are using only constant extra space, the space complexity is O(1).

Code Solution
(100% EXP penalty)
Even Odd Pulse
Full screen
Console