Beautiful Subarrays
Created: October 19, 2019 by [lek-tin]
Last updated: October 19, 2019
Find the distinct subarrays with m odd numbers
Example 1
Input : arr = {2, 5, 6, 9}, m = 2
Output : 2
Explanation: subarrays are [2, 5, 6, 9]
and [5, 6, 9]
Example 2
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]
Solution
python
class Solution:
def countSubarrays(a, n, m):
count = 0
prefix = [0 for _ in range(n)]
odd = 0
# traverse in the array
for i in range(n):
prefix[odd] += 1
# if array element is odd
if (a[i] & 1):
odd += 1
# when number of odd elements>=M
if (odd >= m):
count += prefix[odd - m]
return count