Number of subarrays with m odd numbers | Frustrating question!

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:

  1. Brute force solution O(N**2) is trivial
  2. 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.
  3. 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.
  4. 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!

2 Likes

Yup you said it, that is one interesting question! I remember seeing something similar in a LeetCode Weekend Contest, will try to search for it.

Found it! It was in a Weekly Contest a couple of weeks ago. The intuition behind the solution sounds ingenious.

The key idea is:
Number of subarrays with exactly m odd numbers = number of subarrays with at-most m odd numbers - number of subarrays with at-most m-1 odd numbers.

You can find the solution and the question description at this Leetcode Link

Here’s a quick look at the solution as well from lee215 on LC:

It’s essentially a Two pointer approach, but for the problem of at-most m odd numbers:

def numberOfSubarrays(self, A, k):
        def atMost(k):
            res = i = 0
            for j in xrange(len(A)):
                k -= A[j] % 2
                while k < 0:        
                    k += A[i] % 2
                    i += 1
                res += j - i + 1
            return res

        return atMost(k) - atMost(k - 1)
1 Like