visual walkthrough
Count Number of Nice Subarrays
The same trick applied to odd-number counts.
The idea
Only the parity matters, so mark odd numbers 1 and even numbers 0. A nice subarray is then a subarray whose 0/1 sum is exactly k.
That is the same problem as "binary subarrays with sum": count with an "at most" window twice and subtract.
Complexity
| approach | time | space |
|---|---|---|
| Try every subarray | O(n²) | O(1) |
| atMost(k) − atMost(k−1) | O(n) | O(1) |