Home » Technical Interview Questions » Array Interview Questions » Find the Subarray of given length with Least Average

# Find the Subarray of given length with Least Average

Given an array and an input integer X, write a program to find the subarray of length X with least/minimum average

Prints the starting and ending indexes of the subarray which has the least average.

### Example

INPUT :
arr[] = {3, 5, 1, 7, 6}
X = 2

OUTPUT :
subarray is between index 1 and 2

In the above example we can see that the sum of 5 and  1 is the least.

Time Complexity : O(n)

In this method we use the idea of sliding window of size X.

## Algorithm

1. Initialize index =0, which is the starting index of the subarray with least average

2. Find the sum of first X elements and store it in sum variable

3. Initialize least_sum to the above sum variable

4. Traverse the array from (X+1)th index till end of the array
a. For every element arr[i], calculate sum = sum + arr[i] -arr[i-X]
b. If sum < least_sum, then make index = (i-X+1) and least_sum =sum.

5. Print the index and the index + X -1 as the starting and ending of the subarray with least average. ## C++ Program

```#include <bits/stdc++.h>
using namespace std;
int lavgSubarray(int arr[],int X,int n)
{
int index, sum =0;  //index is for keeping track of starting of least avg subarrray
//sum is to calculate the sum of all subarays
for (int i = 0; i < X; ++i)
{
sum = sum + arr[i];
}
int least_sum = sum;

for (int i = X; i < n; ++i) //moving the window of size X.
{
sum = sum + arr[i] - arr[i-X];
if(sum<least_sum)
{
least_sum = sum;
index = (i-X+1);
}
}
cout<<"subarray in between indexes "<<index<<", "<<index+X-1<<" has least average";
}
int main()
{
int arr[] = {3, 5, 1, 7, 6};
int X= 2;					//subarray length
int n = sizeof(arr)/sizeof(arr);
lavgSubarray(arr,X,n);
}```

READ  Dividing Array into Pairs With Sum Divisible by K
 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions