Program to Count Subarrays with K Odd Numbers.

Given an integer array containing n elements and an integer value k, we need to write a program to count the number of continuous subarrays in the given array that contain k number of odd numbers.

Example:

Input: arr[] = {3, 1, 2, 1, 1}, k = 3
Output: 2
Explanation:
Subarrays with 3 odd numbers are {3, 1, 2, 1} and {1, 2, 1, 1}. 

Input: arr[] = {2, 1, 9, 3, 1}, k = 2
Output: 4
Explanation:
Subarrays with 2 odd numbers are 
{1, 9} {9, 3} {3, 1} {2, 1, 9}

This problem can be solved by multiple approaches, let's discuss each of them one by one with efficiency.

Approach 1: Brute Force.

The brute force approach involves considering all possible subarrays of the given array and checking each subarray to see if it contains exactly k odd numbers.

Below is the C++ code implementation for this approach.

//C++ code to Count Subarrays with K Odd Numbers.
//Brute force
#include<iostream>
#include <vector>
using namespace std;

//function to return count of subarrays
//with k odd numbers
int countOddSubarrays(vector<int>& nums, int k) {
    int n = nums.size();
    int count = 0;
    
    //traverse for all possible subarrays
    for (int i = 0; i < n; i++) {
        int oddCount = 0;
        for (int j = i; j < n; j++) {
            if (nums[j] % 2 == 1) {
                oddCount++;
            }
            if (oddCount == k) {
                count++;
            }
        }
    }

    return count;
}

int main(){
    vector<int> nums = {1, 2, 1, 1, 4, 1};
    int k = 3;

    cout << countOddSubarrays(nums, k);
}

Output:

Time Complexity: O(n^2), because we are using the nested loop to check all possible subarrays.

Space Complexity: O(1), as it does not use any extra space to solve this problem.

Approach 2: Sliding Window Approach.

In this approach, we begin by initializing two pointers, start and end, both pointing to the first element of the array. Additionally, we set count and ans to zero.

The next step involves traversing the array using the end pointer. During this traversal, we increment the count variable if the element is odd. We then slide the window to the right until the count becomes equal to k.

With each step, we update the ans variable to keep track of the number of subarrays containing exactly k odd integers. Eventually, we return the value of ans.

To calculate the number of subarrays with exactly k odd integers, we compute the difference between the number of subarrays with less than k odd integers and the number of subarrays with at most k-1 odd integers. Remarkably, we can leverage the same subArray function to compute both of these values efficiently.

Below is the C++ code implementation for the above approach.

//C++ code to Count Subarrays with K Odd Numbers.
//Sliding window approach
#include<iostream>
#include <vector>
using namespace std;

int subArray(vector<int>& nums, int k) {
    int count = 0, ans = 0, start = 0, end = 0;
    int n = nums.size();

    // Sliding window approach
    while(end<n){
        if(nums[end]%2==1){
            count++;
        }
        // Shrink the window until the count 
        //becomes less than or equal to K
        while(count>k){
            if(nums[start]%2==1){
                count--;
            }
            start++;
        }
        ans += end-start+1;
        end++;
    }
    return ans;
}
// Function to count the number of 
//subarrays with K odd numbers
int countOddSubarrays(vector<int>& nums, int k) {
    /*
    difference between number of subarrays with at most k-1
    odd elements with number of subarrays with at most k
    odd elements
    */
    return subArray(nums, k) - subArray(nums, k - 1);
}

int main(){
    vector<int> nums = {2, 1, 9, 3, 1};
    int k = 2;

    cout << countOddSubarrays(nums, k);
}

Output:

Time Complexity: O(n)

Space Complexity: O(1)

(getButton) #text=(Sliding Window Explanation with Example) #icon=(link) #color=(#2339bd)

Program to Count Subarrays with K Odd Numbers.

Approach 1: Brute Force.

Approach 2: Sliding Window Approach.

No comments:

Post a Comment