Count Distinct Subarrays With At Most K Odd Elements

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'

Approach:

To count the distinct subarrays with exactly 'k' odd elements, we can use the sliding window technique. The idea is to maintain a window that contains at most 'k' odd elements. We will use two pointers, 'i' and 'j', to define the window. The right pointer 'i' will expand the window by moving forward, and the left pointer 'j' will contract the window when the count of odd elements in the window exceeds 'k'.

Algorithm:

distinctSubKOdds(arr, k):

• Initialize the right pointer 'i' to the start of the array.
• Initialize the left pointer 'j' to the start of the array.
• Initialize the final result 'ans' to 0.
• Initialize frequency ‘f’ of having 'k' odd elements in the window to zero.
• Initialize the count ‘c’ of odd elements in the current window to 0.
• while i < arr.length:
  • if arr[i] is odd:
    • c++
  • if c == k:
    • f++
  • if c > k
    • while c > k:
      • if arr[j] is odd:
        • c--
      • j++
      • ans += f
    • f = 1
  • i++
• while c == k:
  • if arr[j] is odd:
    • c--
  • j++
  • ans += f
• return 'ans'