The 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 an average 3.5 greater than k = 3.
An easy approach is to consider each subarray one by one and find its average. If the average value is greater than or equal to k, then compare the length of the subarray with the maximum length found so far in the array. This approach has a time complexity of O(n^2).
@@coding::1@@
Time complexity: O(n)
An algorithm using binary search is given as follows:
@@coding::2@@
Time complexity: O (n log n)
Recommended Programs