Find the longest subsequence of an array having LCM at most K | Java implementation of the approach ; 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
import java . util . * ; class GFG { static void findSubsequence ( int [ ] arr , int n , int k ) { HashMap < Integer , Integer > M = new HashMap < Integer , Integer > ( ) ; for ( int i = 0 ; i < n ; ++ i ) { if ( M . containsKey ( arr [ i ] ) ) M . put ( arr [ i ] , M . get ( arr [ i ] ) + 1 ) ; else M . put ( arr [ i ] , 1 ) ; } int [ ] numCount = new int [ k + 1 ] ; for ( int i = 0 ; i <= k ; ++ i ) numCount [ i ] = 0 ; Iterator < HashMap . Entry < Integer , Integer > > itr = M . entrySet ( ) . iterator ( ) ; while ( itr . hasNext ( ) ) { HashMap . Entry < Integer , Integer > entry = itr . next ( ) ; if ( entry . getKey ( ) <= k ) { for ( int i = 1 ; ; ++ i ) { if ( entry . getKey ( ) * i > k ) break ; numCount [ entry . getKey ( ) * i ] += entry . getValue ( ) ; } } else break ; } int lcm = 0 , length = 0 ; for ( int i = 1 ; i <= k ; ++ i ) { if ( numCount [ i ] > length ) { length = numCount [ i ] ; lcm = i ; } } if ( lcm == 0 ) System . out . println ( - 1 ) ; else { System . out . println ( " LCM ▁ = ▁ " + lcm + " ▁ Length ▁ = ▁ " + length ) ; System . out . print ( " Indexes ▁ = ▁ " ) ; for ( int i = 0 ; i < n ; ++ i ) if ( lcm % arr [ i ] == 0 ) System . out . print ( i + " ▁ " ) ; } } public static void main ( String [ ] args ) { int k = 14 ; int arr [ ] = { 2 , 3 , 4 , 5 } ; int n = arr . length ; findSubsequence ( arr , n , k ) ; } }