Count Number of Nice Subarrays

Problem Statement

The task is to find the number of continuous subarrays in a given array of integers (nums) that contain exactly k odd numbers. These subarrays are termed as "nice" subarrays. The input to the function will be the array nums and the integer k. The output should be an integer representing how many such "nice" subarrays exist.

Examples

Example 1

Input:

nums = [1,1,2,1,1], k = 3

Output:

2

Explanation:

The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].

Example 2

Input:

nums = [2,4,6], k = 1

Output:

0

Explanation:

There are no odd numbers in the array.

Example 3

Input:

nums = [2,2,2,1,2,2,1,2,2,2], k = 2

Output:

16

Constraints

• 1 <= nums.length <= 50000
• 1 <= nums[i] <= 10^5
• 1 <= k <= nums.length

Approach and Intuition

The problem involves analyzing subarrays for a specific count of odd numbers. Given the constraints and nature of the problem, a brute-force solution could be too slow, especially with large arrays. Here's an approach to solve the problem efficiently:

1. Transform the Problem:
   Simplify the problem by focusing only on the odd numbers in nums. Convert nums into a binary representation where 1 denotes an odd number and 0 denotes an even number.

2. Use Prefix Sum and HashMap:

   • The idea is to use a prefix sum to count odd numbers up to each index.
   • Create a hashmap to store how many times each count of odd numbers has been seen as a prefix sum.
   • For each element, calculate the current count of odd numbers using the prefix sum.
   • The key insight is that if at some index i the prefix sum is p, and we have previously seen p-k x times (using the hashmap), then there are x subarrays ending at i which have k odd numbers.

3. Iterate Through Nums:

   • Initialize the hashmap with {0: 1} to handle the case where a subarray with exactly k odd numbers starts from the beginning.
   • As you iterate through nums, update the prefix sum based on whether the current number is odd.
   • For each updated prefix sum, calculate how many times the (current prefix sum) - k has occurred, as it will give the count of subarrays ending at this position that are "nice".

4. Count "Nice" Subarrays:

   • For each index, update the count of "nice" subarrays by adding the count found in the previous step.
   • Also, update the hashmap to reflect the current prefix sum count.

Using the data from the examples:

• For nums = [1,1,2,1,1] and k = 3, convert to [1,1,0,1,1]:
  • The prefix sums would be [1, 2, 2, 3, 4] and you determine counts of reaching each prefix sum considering k.

Considering this method is efficient and direct, it caters well to the constraints provided, specifically handling large arrays up to the length of 50,000.

Solutions

class Solution {
public:
    int countKSubarrays(vector<int>& nums, int k) {
        return atMostK(nums, k) - atMostK(nums, k - 1);
    }
    
private:
    int atMostK(vector<int>& nums, int k) {
        int count = 0, result = 0, left = 0;
    
        for (int right = 0; right < nums.size(); right++) {
            count += nums[right] % 2;
    
            while (count > k) {
                count -= nums[left] % 2;
                left++;
            }
            result += right - left + 1;
        }
    
        return result;
    }
};