Count number of Nice subarrays
HardOdd numbers are 1s in disguise
Problem
Count subarrays containing exactly k odd numbers.
Count windows with at most k odds minus at most k-1 — the difference is exactly k odds.
The idea
Replace each value by its parity and the question becomes 'count subarrays whose sum is exactly k', which is the binary-subarrays problem. The same atMost(k) - atMost(k-1) trick then applies unchanged.
The trick
- Map odd to 1 and even to 0 — no need to build the new array explicitly.
- Reuse exactly(k) = atMost(k) - atMost(k-1).
1
1
2
1
1
0
1
2
3
4
k3
Step 1 of 17. Brute force: count every subarray with exactly 3 odd numbers. Values: 1, 1, 2, 1, 1. k 3.
1/17
Brute force
timeO(n²)spaceO(1)
Every subarray.
1for (let i = 0; i < n; i++) {2 let odds = 0;3 for (let j = i; j < n; j++) {4 if (nums[j] % 2) odds++;5 if (odds === k) count++;6 }7}Input
- array
- [1, 1, 2, 1, 1]
Memory
- k
- 3
Output
- count
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 1, 2, 1, 1], k = 3
- Output:
- 2
- Explanation:
- 2 subarrays contain exactly 3 odds.
Example 2
- Input:
- nums = [2, 4, 6], k = 1
- Output:
- 0
- Explanation:
- No odds at all → 0.
Example 3
- Input:
- nums = [1, 1, 1], k = 2
- Output:
- 2
- Explanation:
- Two windows have exactly 2 odds.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.