Given an integer array arr[] of size n, and a target integer k. Determine the number of contiguous subarrays (i.e., continuous segments of the array) that contain exactly k odd numbers.
A subarray is defined as a non-empty sequence of consecutive elements from the array.
Examples :
Input : arr = [2, 5, 6, 9], k = 2
Output: 2
Explanation: There are 2 subarrays with 2 odds: [2, 5, 6, 9] and [5, 6, 9].Input : arr = [2, 2, 5, 6, 9, 2, 11], k = 2
Output: 8
Explanation: There are 8 subarrays with 2 odds: [2, 2, 5, 6, 9], [2, 5, 6, 9], [5, 6, 9], [2, 2, 5, 6, 9, 2], [2, 5, 6, 9, 2], [5, 6, 9, 2], [6, 9, 2, 11] and [9, 2, 11] .
Try it on GfG Practice
Table of Content
[Naive Approach] Generate All Possible Subarrays - O(n2) Time and O(1) Space
The idea is to generate all possible subarrays, and find the count of subarrays with number of odd elements equal to k.
#include <iostream>
#include <vector>
using namespace std;
int countSubarrays(vector<int> &arr, int k) {
int n = arr.size();
int count = 0;
// traverse for all possible subarrays
for (int i = 0; i < n; i++) {
int odd = 0;
for (int j = i; j < n; j++) {
// if current element is odd
if (arr[j] % 2)
odd++;
// if count of odd numbers in
// subarray is k
if (odd == k)
count++;
}
}
return count;
}
int main() {
vector<int> arr = {2, 2, 5, 6, 9, 2, 11};
int k = 2;
cout << countSubarrays(arr, k);
return 0;
}
class GfG {
static int countSubarrays(int[] arr, int k) {
int n = arr.length;
int count = 0;
// traverse for all possible subarrays
for (int i = 0; i < n; i++) {
int odd = 0;
for (int j = i; j < n; j++) {
// if current element is odd
if (arr[j] % 2 != 0)
odd++;
// if count of odd numbers in
// subarray is k
if (odd == k)
count++;
}
}
return count;
}
public static void main(String[] args) {
int[] arr = {2, 2, 5, 6, 9, 2, 11};
int k = 2;
System.out.println(countSubarrays(arr, k));
}
}
def countSubarrays(arr, k):
n = len(arr)
count = 0
# traverse for all possible subarrays
for i in range(n):
odd = 0
for j in range(i, n):
# if current element is odd
if arr[j] % 2 != 0:
odd += 1
# if count of odd numbers in
# subarray is k
if odd == k:
count += 1
return count
if __name__ == "__main__":
arr = [2, 2, 5, 6, 9, 2, 11]
k = 2
print(countSubarrays(arr, k))
using System;
using System.Collections.Generic;
class GfG {
static int countSubarrays(List<int> arr, int k) {
int n = arr.Count;
int count = 0;
// traverse for all possible subarrays
for (int i = 0; i < n; i++) {
int odd = 0;
for (int j = i; j < n; j++) {
// if current element is odd
if (arr[j] % 2 != 0)
odd++;
// if count of odd numbers in
// subarray is k
if (odd == k)
count++;
}
}
return count;
}
public static void Main() {
List<int> arr = new List<int> {2, 2, 5, 6, 9, 2, 11};
int k = 2;
Console.WriteLine(countSubarrays(arr, k));
}
}
function countSubarrays(arr, k) {
let n = arr.length;
let count = 0;
// traverse for all possible subarrays
for (let i = 0; i < n; i++) {
let odd = 0;
for (let j = i; j < n; j++) {
// if current element is odd
if (arr[j] % 2 !== 0)
odd++;
// if count of odd numbers in
// subarray is k
if (odd === k)
count++;
}
}
return count;
}
// Driver Code
let arr = [2, 2, 5, 6, 9, 2, 11];
let k = 2;
console.log(countSubarrays(arr, k));
Output
8
[Expected Approach] Using HashMap - O(n) Time and O(n) Space
The idea is to use a HashMap to track the frequency of prefix subarrays with a given count of odd numbers. For each element, maintain a running count of odd numbers seen so far. If the current odd count is at least
k, then the number of subarrays ending at the current index with exactlykodd numbers is equal toprefix[odd - k]. Update the prefix count map as you iterate through the array.
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int countSubarrays(vector<int> &arr, int k) {
int n = arr.size();
int count = 0;
// to store count of prefix subarrays
// with particular count of odd numbers
unordered_map<int, int> prefix;
prefix[0] = 1;
// to store count of odd numbers
int odd = 0;
for(int i = 0, odd = 0; i < n; i++) {
// if current element is odd
if (arr[i] % 2)
odd++;
// if count of odd numbers in
// subarray is k
if (prefix.count(odd - k) != 0)
count += prefix[odd - k];
prefix[odd]++;
}
return count;
}
int main() {
vector<int> arr = {2, 2, 5, 6, 9, 2, 11};
int k = 2;
cout << countSubarrays(arr, k);
return 0;
}
import java.util.HashMap;
class GfG {
// function to find the count of subarrays with
// number of odd elements equal to k.
static int countSubarrays(int[] arr, int k) {
int n = arr.length;
int count = 0;
// to store count of prefix subarrays
// with particular count of odd numbers
HashMap<Integer, Integer> prefix = new HashMap<>();
prefix.put(0, 1);
// to store count of odd numbers
int odd = 0;
for(int i = 0; i < n; i++) {
// if current element is odd
if (arr[i] % 2 != 0)
odd++;
// if count of odd numbers in
// subarray is k
if (prefix.containsKey(odd - k))
count += prefix.get(odd - k);
prefix.put(odd, prefix.getOrDefault(odd, 0) + 1);
}
return count;
}
public static void main(String[] args) {
int[] arr = {2, 2, 5, 6, 9, 2, 11};
int k = 2;
System.out.println(countSubarrays(arr, k));
}
}
def countSubarrays(arr, k):
n = len(arr)
count = 0
# to store count of prefix subarrays
# with particular count of odd numbers
prefix = {0: 1}
# to store count of odd numbers
odd = 0
for i in range(n):
# if current element is odd
if arr[i] % 2 != 0:
odd += 1
# if count of odd numbers in
# subarray is k
if (odd - k) in prefix:
count += prefix[odd - k]
prefix[odd] = prefix.get(odd, 0) + 1
return count
if __name__ == "__main__":
arr = [2, 2, 5, 6, 9, 2, 11]
k = 2
print(countSubarrays(arr, k))
using System;
using System.Collections.Generic;
class GfG {
static int countSubarrays(List<int> arr, int k) {
int n = arr.Count;
int count = 0;
// to store count of prefix subarrays
// with particular count of odd numbers
Dictionary<int, int> prefix = new Dictionary<int, int>();
prefix[0] = 1;
// to store count of odd numbers
int odd = 0;
for(int i = 0; i < n; i++) {
// if current element is odd
if (arr[i] % 2 != 0)
odd++;
// if count of odd numbers in
// subarray is k
if (prefix.ContainsKey(odd - k))
count += prefix[odd - k];
if (prefix.ContainsKey(odd))
prefix[odd]++;
else
prefix[odd] = 1;
}
return count;
}
public static void Main() {
List<int> arr = new List<int> {2, 2, 5, 6, 9, 2, 11};
int k = 2;
Console.WriteLine(countSubarrays(arr, k));
}
}
function countSubarrays(arr, k) {
let n = arr.length;
let count = 0;
// to store count of prefix subarrays
// with particular count of odd numbers
let prefix = {0: 1};
// to store count of odd numbers
let odd = 0;
for (let i = 0, oddCount = 0; i < n; i++) {
// if current element is odd
if (arr[i] % 2 !== 0)
oddCount++;
// if count of odd numbers in
// subarray is k
if ((oddCount - k) in prefix)
count += prefix[oddCount - k];
prefix[oddCount] = (prefix[oddCount] || 0) + 1;
}
return count;
}
// Driver Code
let arr = [2, 2, 5, 6, 9, 2, 11];
let k = 2;
console.log(countSubarrays(arr, k));
Output
8
[Optimal Approach] Using Subarrays with (k- 1) Odds - O(n) Time and O(1) Space
The idea is to find the count of subarrays with at most k and k - 1 odd elements, then subtract the results to get the count of subarrays with exactly k odd elements. To find count of subarrays with at most x odd elements, run a loop from 0, and for each odd element, increment the counter count by 1. If count > k, then move the second pointer from 0, until count > k, store the length of subarray.
Step by Step Implementation
- First, we create a function atMostX that counts how many subarrays have at most x odd numbers.
- Inside this function, we use a sliding window with two pointers: one pointer i moves through the array, and the other pointer start marks the beginning of the current valid window.
- We keep track of how many odd numbers are in the current window using a variable odd.
- As we move i, if we find an odd number, we increase the odd count.
- If the number of odd elements becomes more than x, we shrink the window from the left by moving start forward. If the element at start is odd, we decrease the odd count.
- For every valid position of i, the number of subarrays ending at i with at most x odd numbers is (i - start + 1). We add this to our total answer.
- Once we finish the loop, we return the total count from atMostX.
- To count subarrays with exactly k odd numbers, we call atMostX twice — once with k, and once with k - 1.
- The final result is the difference between these two values, because:
=> atMostX(k) counts all subarrays with up to k odd numbers.
=> atMostX(k - 1) counts those with fewer than k odd numbers.
=> Their difference gives us the count with exactly k odd numbers.
#include <iostream>
#include <vector>
using namespace std;
// to find count of subarrays with
// at most x odd elements
int atMostX(vector<int> &arr, int x){
int n = arr.size();
int odd = 0;
int ans = 0;
// to mark the start of the subarray
int start = 0;
for(int i = 0; i < n; i++) {
// if current element is odd
if (arr[i] % 2)
odd++;
// if count of odd elements is greater than x
// then remove elements from the start
while (odd > x) {
if (arr[start] % 2)
odd--;
start++;
}
// add the number of subarrays with at most x
// odd elements ending at the current index
ans += i - start + 1;
}
return ans;
}
// function to find the count of subarrays with
// number of odd elements equal to k.
int countSubarrays(vector<int> &arr, int k) {
int n = arr.size();
// find count of subarrays with at most
// k and k - 1 odd elements
int x = atMostX(arr, k);
int y = atMostX(arr, k - 1);
return x - y;
}
int main() {
vector<int> arr = {2, 2, 5, 6, 9, 2, 11};
int k = 2;
cout << countSubarrays(arr, k);
return 0;
}
class GfG {
// to find count of subarrays with
// at most x odd elements
static int atMostX(int[] arr, int x) {
int n = arr.length;
int odd = 0;
int ans = 0;
// to mark the start of the subarray
int start = 0;
for (int i = 0; i < n; i++) {
// if current element is odd
if (arr[i] % 2 != 0)
odd++;
// if count of odd elements is greater than x
// then remove elements from the start
while (odd > x) {
if (arr[start] % 2 != 0)
odd--;
start++;
}
// add the number of subarrays with at most x
// odd elements ending at the current index
ans += i - start + 1;
}
return ans;
}
// function to find the count of subarrays with
// number of odd elements equal to k.
static int countSubarrays(int[] arr, int k) {
int n = arr.length;
// find count of subarrays with at most
// k and k - 1 odd elements
int x = atMostX(arr, k);
int y = atMostX(arr, k - 1);
return x - y;
}
public static void main(String[] args) {
int[] arr = {2, 2, 5, 6, 9, 2, 11};
int k = 2;
System.out.println(countSubarrays(arr, k));
}
}
# to find count of subarrays with
# at most x odd elements
def atMostX(arr, x):
n = len(arr)
# to store count of odd elements
odd = 0
ans = 0
start = 0
for i in range(n):
# if current element is odd
if arr[i] % 2 != 0:
odd += 1
# if count of odd elements is greater than x
# then remove elements from the start
while odd > x:
if arr[start] % 2 != 0:
odd -= 1
start += 1
# add the number of subarrays with at most x
# odd elements ending at the current index
ans += i - start + 1
return ans
# function to find the count of subarrays with
# number of odd elements equal to k.
def countSubarrays(arr, k):
n = len(arr)
# find count of subarrays with at most
# k and k - 1 odd elements
x = atMostX(arr, k)
y = atMostX(arr, k - 1)
return x - y
if __name__ == "__main__":
arr = [2, 2, 5, 6, 9, 2, 11]
k = 2
print(countSubarrays(arr, k))
using System;
using System.Collections.Generic;
class GfG {
// to find count of subarrays with
// at most x odd elements
static int atMostX(List<int> arr, int x) {
int n = arr.Count;
int odd = 0;
int ans = 0;
// to mark the start of the subarray
int start = 0;
for (int i = 0; i < n; i++) {
// if current element is odd
if (arr[i] % 2 != 0)
odd++;
// if count of odd elements is greater than x
// then remove elements from the start
while (odd > x) {
if (arr[start] % 2 != 0)
odd--;
start++;
}
// add the number of subarrays with at most x
// odd elements ending at the current index
ans += i - start + 1;
}
return ans;
}
// function to find the count of subarrays with
// number of odd elements equal to k.
static int countSubarrays(List<int> arr, int k) {
int n = arr.Count;
// find count of subarrays with at most
// k and k - 1 odd elements
int x = atMostX(arr, k);
int y = atMostX(arr, k - 1);
return x - y;
}
public static void Main() {
List<int> arr = new List<int> {2, 2, 5, 6, 9, 2, 11};
int k = 2;
Console.WriteLine(countSubarrays(arr, k));
}
}
// to find count of subarrays with
// at most x odd elements
function atMostX(arr, x) {
let n = arr.length;
let odd = 0;
let ans = 0;
// to mark the start of the subarray
let start = 0;
for (let i = 0; i < n; i++) {
// if current element is odd
if (arr[i] % 2 !== 0)
odd++;
// if count of odd elements is greater than x
// then remove elements from the start
while (odd > x) {
if (arr[start] % 2 !== 0)
odd--;
start++;
}
// add the number of subarrays with at most x
// odd elements ending at the current index
ans += i - start + 1;
}
return ans;
}
// Function to find the count of subarrays with
// number of odd elements equal to k.
function countSubarrays(arr, k) {
let n = arr.length;
// find count of subarrays with at most
// k and k - 1 odd elements
let x = atMostX(arr, k);
let y = atMostX(arr, k - 1);
return x - y;
}
// Driver Code
let arr = [2, 2, 5, 6, 9, 2, 11];
let k = 2;
console.log(countSubarrays(arr, k));
Output
8