Count Distinct Subarrays With At Most K Odd Elements

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
37 upvotes
Asked in companies
BNY MellonJio Platforms LimitedRedBus

Problem statement

You are given an array 'arr' of 'N' integers. Your task is to return the total number of distinct subarrays of 'arr' having 'k' odd elements.


Example : 
If arr = [3,2,3], and k = 1 
then there are 4 subarrays with 1 odd elements:
[3], [3,2], [2,3] & [3].
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line contains single space-separated two integers 'N' and 'k'.

The second line contains 'N' space-separated integers, denoting the elements of array 'arr'.
Output format : 
The output contains the number of distinct subarrays with 'k' odd elements.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1
5 2
2 1 1 1 4
Sample Output 1 :
4
Explanation for sample input 1 :
Following are 3 valid subarray:
[2,1,1], [1,1], [1,1], [1,1,4].
Sample Input 2 :
3 2
1 3 1
Sample Output 2 :
2
Constraints :
1 <= N <= 10^4
0 <= k <= N
1 <= arr[i] <= 10 ^ 5

Time Limit: 1sec
Hint

Approach is similar to “subarray sum equals k”.

Approaches (2)
Hashmap approach

Approach:

The idea is to maintain a count of odd numbers encountered so far and use a hashmap to keep track of frequency of different counts. This approach is similar to the approach used in finding subarray of sum k.

 

Algorithm: 

function distinctSubKOdds(arr, k):

  • Initialize ‘c’ = 0
  • Initialize ‘ans’ = 0
  • Initialize ‘mp’ = create_empty_hashmap()
  • for i = 0 to arr.size() - 1:
    • if arr[i] % 2 == 1:
      • c += 1
    • if c == k:
      • ans += 1
    • if mp.contains(c - k):
      • ans += mp[c - k]
    • mp[c] += 1
  • return 'ans'
Time Complexity

O(N ), where ‘N’ is the length of the given array.

 

The reason for this linear time complexity is that we only traverse the array once using a single loop. Within the loop, all the operations like incrementing counters, hashmap lookups, and updates take constant time.

Space Complexity

O(N ), where ‘N’ is the length of the given array.

 

The space usage comes from the hashmap 'mp' that stores the count of odd numbers encountered. In the worst case, if all elements in the array are distinct and odd, the hashmap can contain ‘N’ unique keys (one for each element).

Code Solution
(100% EXP penalty)
Count Distinct Subarrays With At Most K Odd Elements
Full screen
Console