Longest subsequence whose average is less than K | Java 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 java . util . Arrays ; class GFG { static void longestSubsequence ( int a [ ] , int n , int q [ ] , int m ) { Arrays . sort ( a ) ; int sum = 0 ; int [ ] b = new int [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { sum += a [ i ] ; double av = ( double ) ( sum ) / ( double ) ( i + 1 ) ; b [ i ] = ( ( int ) ( av + 1 ) ) ; } Arrays . sort ( b ) ; for ( int i = 0 ; i < m ; i ++ ) { int k = q [ i ] ; int longest = upperBound ( b , 0 , n , k ) ; System . out . println ( " Answer ▁ to ▁ Query " + ( i + 1 ) + " : ▁ " + longest ) ; } } private static int upperBound ( int [ ] a , int low , int high , int element ) { while ( low < high ) { int middle = low + ( high - low ) / 2 ; if ( a [ middle ] > element ) high = middle ; else low = middle + 1 ; } return low ; } public static void main ( String [ ] args ) { int a [ ] = { 1 , 3 , 2 , 5 , 4 } ; int n = a . length ; int q [ ] = { 4 , 2 , 1 , 5 } ; int m = q . length ; longestSubsequence ( a , n , q , m ) ; } }