Intermediate Level
Implement the countNiceSubarrays method that counts subarrays that contain exactly k odd numbers.
The input contains an integer array nums, its length size, and an integer k. A nice subarray is a continuous subarray that contains exactly k odd numbers.
Your task is to count how many nice subarrays exist in the given array.
For example, in [1,1,2,1,1] with k = 3, there are 2 such subarrays.
Example 1
Input
nums (int[]) =
[1,1,2,1,1]size (int) =
5k (int) =
3Returns (int)
2Example 2
Input
nums (int[]) =
[2,4,6]size (int) =
3k (int) =
1Returns (int)
0Example 3
Input
nums (int[]) =
[2,2,2,1,2,2,1,2,2,2]size (int) =
10k (int) =
2Returns (int)
16Track how many odd numbers have been seen so far using a prefix count.
For each position, calculate the current number of odd values seen. To form a subarray with exactly k odd numbers, we need an earlier prefix with odd count equal to currentOddCount - k.
Store how many times each prefix odd count has occurred. Add that stored count to the answer for every position.
Pseudocode:
function countNiceSubarrays(nums, size, k):
prefixFrequency = empty map
prefixFrequency[0] = 1
oddCount = 0
answer = 0
for i from 0 to size - 1:
if nums[i] is odd:
oddCount++
needed = oddCount - k
if needed exists in prefixFrequency:
answer = answer + prefixFrequency[needed]
prefixFrequency[oddCount]++
return answerReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run