CODEWITHSUNDEEP
arraysalgorithm
John Doe
John Doe

Reputation: 21

Count sub arrays with atmost k odd numbers

I recently encountered a question as follows.

Given an array, count number of distinct sub-arrays which have at most m odd numbers.

I know how to solve for exactly m odd numbers. Was wondering can this be solved in O(n) too? Any ideas?

Upvotes: 2

Views: 2904

Answers (1)

Gassa
Gassa

Reputation: 8846

The solution for exactly m odd numbers likely finds, for each starting point i, the rightmost endpoint r(i) of such a sub-array.

What's left is to say that, for at most m odd numbers, each starting point i has r(i) - i + 1 possibilities for an endpoint.

Upvotes: 2

Related Questions