Given an array of n elements and an integer m, we need to write a program to find the number of contiguous subarrays in the array which contains exactly m odd numbers.

Input : arr = {2, 5, 6, 9}, m = 2

Output : 2

Explanation: subarrays are [2, 5, 6, 9]

and [5, 6, 9]

Input : arr = {2, 2, 5, 6, 9, 2, 11}, m = 2

Output : 8

Explanation: subarrays are [2, 2, 5, 6, 9],

[2, 5, 6, 9], [5, 6, 9], [2, 2, 5, 6, 9, 2],

[2, 5, 6, 9, 2], [5, 6, 9, 2], [6, 9, 2, 11]

and [9, 2, 11]

Notes:

- Brute force solution O(N**2) is trivial
- There is a solution with O(N) time and O(N) space - explained here: https://www.geeksforgeeks.org/number-subarrays-m-odd-numbers/ but it is so badly explained + written that it hurts reading through it.
- A few of us tried a sliding window-based approach in the Interview Reflection session but came to a consensus that it’s probably not the best way to do it.
- A friend of mine got this question as one of the problems in an IBM online coding assessment for an SWE position.

If anyone could come up with a good explanation for the solution in (2) above, or better write a good one, it would be super helpful!

Thank you!