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[0]); lavgSubarray(arr,X,n); }