97. Exactly K Odd
A bakery counts how many loaves each oven produced in a series of consecutive batches; the array nums holds those counts in order. The manager likes to audit contiguous stretches of batches and cares only about how many of the batches in a stretch produced an odd number of loaves.
Given the integer k, count how many contiguous, non-empty stretches (subarrays) of nums contain exactly k odd numbers. Stretches at different positions count separately even if they hold identical values. Return the total count.
Example 1
- Input:
- nums = [1,2,3,2,5], k = 2
- Output:
- 4
- Explanation:
The stretches with exactly two odd numbers are [1,2,3], [1,2,3,2], [3,2,5] and [2,3,2,5], so the answer is 4.
Example 2
- Input:
- nums = [4,6,8], k = 1
- Output:
- 0
- Explanation:
There are no odd numbers at all, so no stretch has exactly one and the answer is 0.
Constraints
- 1 ≤ nums.length ≤ 50000
- 1 ≤ nums[i] ≤ 106
- 0 ≤ k ≤ nums.length
The answer always fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)