Table of Contents

## 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.