Longest subsequence whose average is less than K | Python3 program to perform Q queries to find longest subsequence whose average is less than K ; Function to print the length for evey query ; sort array of N elements ; Array to store average from left ; Sort array of average ; number of queries ; print answer to every query using binary search ; Driver Code ; 4 queries
import bisect NEW_LINE def longestSubsequence ( a , n , q , m ) : NEW_LINE INDENT a . sort ( ) NEW_LINE Sum = 0 NEW_LINE b = [ None ] * n NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT Sum += a [ i ] NEW_LINE av = Sum // ( i + 1 ) NEW_LINE b [ i ] = av + 1 NEW_LINE DEDENT b . sort ( ) NEW_LINE for i in range ( 0 , m ) : NEW_LINE INDENT k = q [ i ] NEW_LINE longest = bisect . bisect_right ( b , k ) NEW_LINE print ( " Answer ▁ to ▁ Query " , i + 1 , " : " , longest ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 1 , 3 , 2 , 5 , 4 ] NEW_LINE n = len ( a ) NEW_LINE q = [ 4 , 2 , 1 , 5 ] NEW_LINE m = len ( q ) NEW_LINE longestSubsequence ( a , n , q , m ) NEW_LINE DEDENT