Runs with Exactly k Odd Numbers

Given a list of positive integers nums and an integer k, return the number of contiguous subarrays that contain exactly k odd numbers.

Examples

Input:  nums = [1, 1, 2, 1, 1], k = 3
Output: 2
Explanation: [1,1,2,1] and [1,2,1,1].

Input:  nums = [2, 4, 6], k = 1
Output: 0

Input:  nums = [2, 2, 2, 1, 2, 2, 1, 2, 2, 2], k = 2
Output: 16

Constraints

• 1 <= len(nums) <= 10**5
• 1 <= nums[i] <= 10**5, 1 <= k <= len(nums)
• Target complexity: O(n) time; checking every subarray is too slow for the largest tests.

Goals

• Turn an 'exactly k' count into a difference of two 'at most' counts
• Count subarrays with at most k of something in one sliding pass