Last Updated: 9 Jun, 2022
Even Odd Pulse
Moderate
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.
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
Approaches
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.
Approach:-
- We can use two-pointer method to solve this problem more efficiently. We will keep two pointers i.e. left and right to maintain some segment of the array 'A' i.e. 'A[left…right]' and will also maintain the count of the number of even and odd numbers in that segment.
- We will move both pointers of this segment to the right. If we move the right pointer one element forward, and if the 'Pulse' of the new segment is less than 'K', then we can leave the left pointer in place. We do not move the left pointer as long as the pulse remains below 'K'.
- Now, If we we add an element from the right pointer and the 'Pulse' has become more than or equal to 'K', then we can move the left pointer forward. We need to move it forward until the 'Pulse' of the segment again becomes less than 'K'.
- While moving from 'A[left…right]' to 'A[left+1…right+1]' we can just remove the contribution of 'A[left]' from the count of number of even and odd elements, and add the contribution of 'A[right+1]' to it. Using this method, we won't need to calculate the count of the number of even and odd elements for 'A[left+1…right+1]' again.
Algorithm:-
- Initialize an integer variable 'minLength' = 'INT_MAX' to store the minimum possible length.
- Initialize integer variables 'left' = 0 and 'right' = 0, to maintain the left and the right pointers.
- Initialize integer variables 'evenCount' = 0 and 'oddCount' = 0, to store number of even elements and number of odd elements respectively.
- Run a while loop with condition 'right<N'.
- If 'A[right]' is odd, increment 'oddCount' .
- Else increment 'evenCount'.
- If 'oddCount*evenCount >= K', run a while loop with condition 'oddCount*evenCount >= K'.
- Update 'minLength' to min('minLength', 'right' - 'left' + 1).
- If 'A[left]' is odd, decrement 'oddCount' .
- Else decrement 'evenCount'.
- Increment 'left'.
- Increment 'right'.
- 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.