Link copied to clipboard. Share away!

Dissmis

Published on 10 Mar 2020

Program to find the longest subarray having an average greater than or equal to k is discussed here. An array and a positive integer (k) are given as input. A subarray from the array has to be found such that the average of this subarray is greater than or equal to x.

For example,

Consider the array:** arr = {-2, 1, 6, -3} and k = 3. **The longest subarray is {1, 6} having average 3.5 greater than k = 3.

An** easy approach** is to consider each sub array one by one and find its average. If the average value is greater than or equal to k, then compare the length of subarray with maximum length found so far in the array. This approach has a time complexity of O(n^2).

C

C++

Output

Enter the number of elements : 4

Input the array elements : -2 1 6 -3

Input the k value : 3

Sub-array average : 2

Input the array elements : -2 1 6 -3

Input the k value : 3

Sub-array average : 2

**Time complexity:** O(n)

An algorithm using binary search is given as follows:

- Input the array elements and the value 'k' (The output average should be greater than this value 'k')
- The value 'k' is subtracted from each element of the array.
- Create a vector and store the updated sum values during each iteration.
- Sort this vector and create a variable min_index to store the minimum index of the value stored in the vector.
- For i = 0 to length of the vector,
- Calculate the sum of the vectors. If sum >= 0, then return i+1.
- If sum < 0, find if there is a value in the array (using binary search) which when added to the current sum, the value gets greater than or equal to zero.
- If yes, compare the length of the updated sub-array with the maximum_length.
- Return maximum_length.

C++

Output

Enter the number of elements : 4

Input the array elements : -2 1 6 -3

Input the k value : 3

Sub-array average : 2

Input the array elements : -2 1 6 -3

Input the k value : 3

Sub-array average : 2

**Time complexity: **O (n log n)

*Recommended Programs*

If you have any feedback about this
article and want to improve this, please write to **enquiry@faceprep.in**

×