Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Webinars
About Us

Edit
Reply




Edit

Program to Find the Longest Subarray having average greater than or equal to k

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.


Brute Force approach:


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


Program to find the longest subarray having an average greater than or equal to k


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


Time complexity: O(n)


An efficient approach using binary search:


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.


Program to find the longest subarray having average greater than or equal to k (using binary search)


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


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