Data Modelling & AI Data Structure & Algorithm

Count of subarrays of size K with average at least M

23 June 2025

0

Given an array arr[] consisting of N integers and two positive integers K and M, the task is to find the number of subarrays of size K whose average is at least M.

Examples:

Input: arr[] = {2, 3, 3, 4, 4, 4, 5, 6, 6}, K = 3, M = 4
Output: 4
Explanation:
Below are the subarrays of size K(= 3) whose average is at least M(= 4) as:

arr[3, 5]: The average is 4 which is at least M(= 4).

arr[4, 6]: The average is 4.33 which is at least M(= 4).

arr[5, 7]: The average is 5 which is at least M(= 4).

arr[6, 8]: The average is 5.66 which is at least M(= 4).

Therefore, the count of the subarray is given by 4.

Input: arr[] = {3, 6, 3, 2, 1, 3, 9] K = 2, M = 4
Output: 3

Approach: The given problem can be solved by using the Two Pointers and Sliding Window Technique. Follow the steps below to solve the given problem:

Initialize a variable, say count as 0 that stores the count of all possible subarrays.
Initialize a variable, say sum as 0 that stores the sum of elements of the subarray of size K.
Find the sum of the first K array elements and store it in the variable sum. If the value of sum is at least M*K, then increment the value of count by 1.
Traverse the given array arr[] over the range [K, N – 1] using the variable i and perform the following steps:
- Add the value of arr[i] to the variable sum and subtract the value of arr[i – K] from the sum.
- If the value of sum is at least M*K, then increment the value of count by 1.
After completing the above steps, print the value of count as the resultant count of subarrays.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <iostream>
using namespace std;
 
// Function to count the subarrays of
// size K having average at least M
int countSubArrays(int arr[], int N,
                   int K, int M)
{
    // Stores the resultant count of
    // subarray
    int count = 0;
 
    // Stores the sum of subarrays of
    // size K
    int sum = 0;
 
    // Add the values of first K elements
    // to the sum
    for (int i = 0; i < K; i++) {
        sum += arr[i];
    }
 
    // Increment the count if the
    // current subarray is valid
    if (sum >= K * M)
        count++;
 
    // Traverse the given array
    for (int i = K; i < N; i++) {
 
        // Find the updated sum
        sum += (arr[i] - arr[i - K]);
 
        // Check if current subarray
        // is valid or not
        if (sum >= K * M)
            count++;
    }
 
    // Return the count of subarrays
    return count;
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 6, 3, 2, 1, 3, 9 };
    int K = 2, M = 4;
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << countSubArrays(arr, N, K, M);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG 
{
   
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 3, 6, 3, 2, 1, 3, 9 };
        int K = 2, M = 4;
        System.out.println(countSubArrays(arr, K, M));
    }
   
    // Function to count the subarrays of
    // size K having average at least M
    public static int countSubArrays(int[] arr, int K,
                                     int M)
    {
       
        // Stores the resultant count of
        // subarray
        int count = 0;
 
        // Stores the sum of subarrays of
        // size K
        int sum = 0;
 
        // Add the values of first K elements
        // to the sum
        for (int i = 0; i < K; i++) {
            sum += arr[i];
        }
 
        // Increment the count if the
        // current subarray is valid
        if (sum >= K * M)
            count++;
 
        // Traverse the given array
        for (int i = K; i < arr.length; i++) {
 
            // Find the updated sum
            sum += (arr[i] - arr[i - K]);
 
            // Check if current subarray
            // is valid or not
            if (sum >= K * M)
                count++;
        }
 
        // Return the count of subarrays
        return count;
    }
}
 
// This code is contributed by Kdheeraj.

Python3

# Python 3 code for the above approach
 
# Function to count the subarrays of
# size K having average at least M
def countSubArrays(arr, N, K, M):
   
    # Stores the resultant count of
    # subarray
    count = 0
 
    # Stores the sum of subarrays of
    # size K
    sum = 0
 
    # Add the values of first K elements
    # to the sum
    for i in range(K):
        sum += arr[i]
 
    # Increment the count if the
    # current subarray is valid
    if sum >= K*M:
        count += 1
 
    # Traverse the given array
    for i in range(K, N):
 
        # Find the updated sum
        sum += (arr[i] - arr[i - K])
 
        # Check if current subarray
        # is valid or not
        if sum >= K*M:
            count += 1
 
    # Return the count of subarrays
    return count
 
# Driver Code
if __name__ == '__main__':
    arr = [3, 6, 3, 2, 1, 3, 9]
    K = 2
    M = 4
    N = len(arr)
    count = countSubArrays(arr, N, K, M)
    print(count)
 
    # This code is contributed by Kdheeraj.

C#

// C# program for the above approach
 
using System;
 
public class GFG 
{
   
    // Driver Code
    public static void Main(String[] args)
    {
        int[] arr = { 3, 6, 3, 2, 1, 3, 9 };
        int K = 2, M = 4;
        Console.WriteLine(countSubArrays(arr, K, M));
    }
   
    // Function to count the subarrays of
    // size K having average at least M
    public static int countSubArrays(int[] arr, int K,
                                     int M)
    {
       
        // Stores the resultant count of
        // subarray
        int count = 0;
 
        // Stores the sum of subarrays of
        // size K
        int sum = 0;
 
        // Add the values of first K elements
        // to the sum
        for (int i = 0; i < K; i++) {
            sum += arr[i];
        }
 
        // Increment the count if the
        // current subarray is valid
        if (sum >= K * M)
            count++;
 
        // Traverse the given array
        for (int i = K; i < arr.Length; i++) {
 
            // Find the updated sum
            sum += (arr[i] - arr[i - K]);
 
            // Check if current subarray
            // is valid or not
            if (sum >= K * M)
                count++;
        }
 
        // Return the count of subarrays
        return count;
    }
}
 
// This code is contributed by AnkThon

Javascript

<script>
       // JavaScript Program to implement
       // the above approach
 
       // Function to count the subarrays of
       // size K having average at least M
       function countSubArrays(arr, N,
           K, M) 
       {
           // Stores the resultant count of
           // subarray
           let count = 0;
 
           // Stores the sum of subarrays of
           // size K
           let sum = 0;
 
           // Add the values of first K elements
           // to the sum
           for (let i = 0; i < K; i++) {
               sum += arr[i];
           }
 
           // Increment the count if the
           // current subarray is valid
           if (sum >= K * M)
               count++;
 
           // Traverse the given array
           for (let i = K; i < N; i++) {
 
               // Find the updated sum
               sum += (arr[i] - arr[i - K]);
 
               // Check if current subarray
               // is valid or not
               if (sum >= K * M)
                   count++;
           }
 
           // Return the count of subarrays
           return count;
       }
 
       // Driver Code
       let arr = [3, 6, 3, 2, 1, 3, 9];
       let K = 2, M = 4;
       let N = arr.length;
 
       document.write(countSubArrays(arr, N, K, M));
 
    // This code is contributed by Potta Lokesh
 
   </script>

Output:

Time Complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Count of subarrays of size K with average at least M

C++

Java

Python3

C#

Javascript

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

LEAVE A REPLY Cancel reply

Most Popular

Google TV wants to take your video-watching experience to the next level with a bunch of AI features

I asked NotebookLM to analyze my emails, notes, and chats — and I was surprised by the results

Google Docs wants to bring Gemini’s writing chops to Android

The single best Pixel feature that turned me into a power user

EDITOR PICKS

Google TV wants to take your video-watching experience to the next level with a bunch of AI features

I asked NotebookLM to analyze my emails, notes, and chats — and I was surprised by the results

Google Docs wants to bring Gemini’s writing chops to Android

POPULAR POSTS

Google TV wants to take your video-watching experience to the next level with a bunch of AI features

I asked NotebookLM to analyze my emails, notes, and chats — and I was surprised by the results

Google Docs wants to bring Gemini’s writing chops to Android

POPULAR CATEGORY

ABOUT US

FOLLOW US