Find the longest subsequence of an array having LCM at most K | Function to find the longest subsequence having LCM less than or equal to K ; Map to store unique elements and their frequencies ; Update the frequencies ; Array to store the count of numbers whom 1 <= X <= K is a multiple of ; Check every unique element ; Find all its multiples <= K ; Store its frequency ; Obtain the number having maximum count ; Condition to check if answer doesn 't exist ; Print the answer ; Driver code
function findSubsequence ( arr , n , k ) { let M = new Map ( ) ; for ( let i = 0 ; i < n ; ++ i ) { if ( M . has ( arr [ i ] ) ) { M . set ( arr [ i ] , M . get ( arr [ i ] ) + 1 ) } else { M . set ( arr [ i ] , 1 ) } } let numCount = new Array ( k + 1 ) ; for ( let i = 0 ; i <= k ; ++ i ) numCount [ i ] = 0 ; for ( let p of M ) { if ( p [ 0 ] <= k ) { for ( let i = 1 ; ; ++ i ) { if ( p [ 0 ] * i > k ) break ; numCount [ p [ 0 ] * i ] += p [ 1 ] ; } } else break ; } let lcm = 0 , length = 0 ; for ( let i = 1 ; i <= k ; ++ i ) { if ( numCount [ i ] > length ) { length = numCount [ i ] ; lcm = i ; } } if ( lcm == 0 ) document . write ( - 1 + " " ) ; else { document . write ( " " + lcm + " " + length + " " ) ; document . write ( " " ) ; for ( let i = 0 ; i < n ; ++ i ) if ( lcm % arr [ i ] == 0 ) document . write ( i + " " ) ; } } let k = 14 ; let arr = [ 2 , 3 , 4 , 5 ] ; let n = arr . length ; findSubsequence ( arr , n , k ) ;