human
Longest subarray having average greater than or equal to x | Function to find index in preSum list of tuples upto which all prefix sum values are less than or equal to val ..
Starting and ending index of search space ..
To store required index value.
If middle value is less than or equal to val then index can lie in mid + 1. . n else it lies in 0. . mid - 1.
Function to find Longest subarray having average greater than or equal to x ..
Update array by subtracting x from each element.
Length of Longest subarray ..
list to store pair of prefix sum and corresponding ending index value ..
To store current value of prefix sum ..
To store minimum index value in range 0. . i of preSum vector ..
Insert values in preSum vector.
Update minInd array ..
If sum is greater than or equal to 0 , then answer is i + 1.
If sum is less than 0 , then find if there is a prefix array having sum that needs to be added to current sum to make its value greater than or equal to 0. If yes , then compare length of updated subarray with maximum length found so far.
Driver Code"
Solution in Python:
 ... Write me a code to longest subarray having average greater than or equal to x and the other steps required?
assistant
#Here is code to longest subarray having average greater than or equal to x and the other steps required.
 def findInd ( preSum , n , val ) :
	l = 0
	h = n - 1
	ans = - 1
	while ( l <= h ) :
		mid = ( l + h ) // 2
		if preSum [ mid ] [ 0 ] <= val :
			ans = mid
			l = mid + 1
		else :
			h = mid - 1
	return ans
def LongestSub ( arr , n , x ) :
	for i in range ( n ) :
		arr [ i ] -= x
	maxlen = 0
	preSum = [ ]
	total = 0
	minInd = [ None ] * n
	for i in range ( n ) :
		total += arr [ i ]
		preSum . append ( ( total , i ) )
	preSum = sorted ( preSum )
	minInd [ 0 ] = preSum [ 0 ] [ 1 ]
	for i in range ( 1 , n ) :
		minInd [ i ] = min ( minInd [ i - 1 ] , preSum [ i ] [ 1 ] )
	total = 0
	for i in range ( n ) :
		total += arr [ i ]
		if total >= 0 :
			maxlen = i + 1
		else :
			ind = findInd ( preSum , n , total )
			if ( ind != - 1 ) & ( minInd [ ind ] < i ) :
				maxlen = max ( maxlen , i - minInd [ ind ] )
	return maxlen
if __name__ == ' _ _ main _ _ ' :
	arr = [ - 2 , 1 , 6 , - 3 ]
	n = len ( arr )
	x = 3
	print ( LongestSub ( arr , n , x ) )