Approach Summary
Count subarrays with exactly k odd numbers = at-most-k minus at-most-(k-1). Or prefix count of odd parities.
How to Recognize This Pattern
- "Subarrays with exactly k odd numbers"
- Exactly k = at-most-k − at-most-(k-1)
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
Tags
Array Hash Table Math Sliding Window Prefix Sum