# Find the Subarray of given length with Least Average

Difficulty Level Easy
Frequently asked in Accenture Accolite Amazon Factset Fourkites Paytm Zoho
ArrayViews 538

## Problem Statement

In the “Find the Subarray of given length with Least Average” problem we have 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.

## Input Format

The first line containing an integer value n.

Second-line containing n space-separated integers.

The third line containing an integer value X.

## Output Format

The first and only one line containing two integer values with space-separated. The first integer represents the starting and the second integer represents the ending indexes of the subarray which has the least average.

## Constraints

• 1<=N<=10^5
• 1<=a[i]<=10^9
• 1<=X<=N

## Example

```5
3 5 1 7 6
2```
`1 2`

Explanation: The subarray is between index 1 and 2. We can see clearly that the sum of 5 and  1 is the least.

## Algorithm to Find the Subarray of given length with Least Average

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

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

2. Find the sum of the 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 the end of the array

• For every element arr[i], calculate sum = sum + arr[i] -arr[i-X]
• 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.

## Implementation

### C++ Program to Find the Subarray of given length with Least Average

```#include <bits/stdc++.h>
using namespace std;

int main()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int k;
cin>>k;
if(n>=k)
{
int ans = 0;
int sum = 0;
for(int i=0;i<k;i++)
{
sum+=a[i];
}
int min_sum=sum;
for (int i=k;i<n;i++)
{
sum+=a[i]-a[i-k];
if(sum<min_sum)
{
min_sum = sum;
ans = (i-k+1);
}
}
cout<<ans<<" "<<ans+k-1<<endl;
}
else
{
cout<<-1<<endl;
}
return 0;
}
```

### Java Program to Find the Subarray of given length with Least Average

```import java.util.Scanner;
class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n=sr.nextInt();
int a[]= new int[n];
for(int i=0;i<n;i++)
{
a[i]=sr.nextInt();
}
int k = sr.nextInt();
if(n>=k)
{
int ans = 0;
int sum = 0;
for(int i=0;i<k;i++)
{
sum+=a[i];
}
int min_sum=sum;
for (int i=k;i<n;i++)
{
sum+=a[i]-a[i-k];
if(sum<min_sum)
{
min_sum = sum;
ans = (i-k+1);
}
}
System.out.println(ans +" "+(ans+k-1));
}
else
{
System.out.println(-1);
}
}
}
```
```10
1 4 3 6 23 76 43 1 2 89
4```
`0 3`

## Complexity Analysis to Find the Subarray of given length with Least Average

### Time Complexity

O(n) where n is the size of the given array a[]. Here we use the concept of the sliding window which take linear time.

### Space Complexity

O(1) because we don’t use any auxiliary space at here.

Translate »