Count of Array elements greater than or equal to twice the Median of K trailing Array elements | Python3 program to implement the above approach ; Function to find the count of array elements >= twice the median of K trailing array elements ; Stores frequencies ; Stores the array elements ; Count the frequencies of the array elements ; Iterating from d to n - 1 index means ( d + 1 ) th element to nth element ; To check the median ; Iterate over the frequencies of the elements ; Add the frequencies ; Check if the low_median value is obtained or not , if yes then do not change as it will be minimum ; Check if the high_median value is obtained or not , if yes then do not change it as it will be maximum ; Store 2 * median of K trailing elements ; If the current >= 2 * median ; Decrease the frequency for ( k - 1 ) - th element ; Increase the frequency of the current element ; Print the count ; Driver Code
import math NEW_LINE N = 200000 NEW_LINE V = 500 NEW_LINE def solve ( n , d , input1 ) : NEW_LINE INDENT a = [ 0 ] * N NEW_LINE cnt = [ 0 ] * ( V + 1 ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT a [ i ] = input1 [ i ] NEW_LINE DEDENT answer = 0 NEW_LINE for i in range ( d ) : NEW_LINE INDENT cnt [ a [ i ] ] += 1 NEW_LINE DEDENT for i in range ( d , n ) : NEW_LINE INDENT acc = 0 NEW_LINE low_median = - 1 NEW_LINE high_median = - 1 NEW_LINE for v in range ( V + 1 ) : NEW_LINE INDENT acc += cnt [ v ] NEW_LINE if ( low_median == - 1 and acc >= int ( math . floor ( ( d + 1 ) / 2.0 ) ) ) : NEW_LINE INDENT low_median = v NEW_LINE DEDENT if ( high_median == - 1 and acc >= int ( math . ceil ( ( d + 1 ) / 2.0 ) ) ) : NEW_LINE INDENT high_median = v NEW_LINE DEDENT DEDENT double_median = low_median + high_median NEW_LINE if ( a [ i ] >= double_median ) : NEW_LINE INDENT answer += 1 NEW_LINE DEDENT cnt [ a [ i - d ] ] -= 1 NEW_LINE cnt [ a [ i ] ] += 1 NEW_LINE DEDENT print ( answer ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT input1 = [ 1 , 2 , 2 , 4 , 5 ] NEW_LINE n = len ( input1 ) NEW_LINE k = 3 NEW_LINE solve ( n , k , input1 ) NEW_LINE DEDENT