Better Approach

Algorithm

Instead of checking every possible subarray, we can speed things up by using prefix sums and a hashmap. We focus on counting how many subarrays have exactly k odd numbers. So, for each index we track how many odd numbers we’ve seen so far. If we’ve seen oddCount odds up to index i, and there was a previous prefix where we had (oddCount-k), then the subarray between those two points has exactly k odd numbers.

We use a hashmap to store the count of how many times each oddCount has occurred. As we traverse the array, we just lookup how many times we’ve seen (oddCount-k) and add that to the answer.

Use a frequency map to track how often a certain count of odd numbers has occurred in the prefix of the array.
Start by adding a base case to the map: zero odd numbers seen so far has occurred once.
Start traversing the array from left to right:

For each element, check if it is odd. If it is, increase the running count of odd numbers seen so far.
Check if the frequency map contains the value equal to the current count of odd numbers minus the required count. If yes, it means there are subarrays ending at the current index with exactly the required count of odd numbers. Add the frequency of that value to the final answer.
Update the frequency map by increasing the count of the current odd-number total.

Once the entire array is processed, return the accumulated answer as the total number of valid subarrays.