Find the longest subsequence of an array having LCM at most K | C # 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
using System ; using System . Collections . Generic ; class GFG { static void findSubsequence ( int [ ] arr , int n , int k ) { Dictionary < int , int > M = new Dictionary < int , int > ( ) ; for ( int i = 0 ; i < n ; ++ i ) { if ( M . ContainsKey ( arr [ i ] ) ) M [ arr [ i ] ] ++ ; else M [ arr [ i ] ] = 1 ; } int [ ] numCount = new int [ k + 1 ] ; for ( int i = 0 ; i <= k ; ++ i ) numCount [ i ] = 0 ; Dictionary < int , int > . KeyCollection keyColl = M . Keys ; foreach ( int key in keyColl ) { if ( key <= k ) { for ( int i = 1 ; ; ++ i ) { if ( key * i > k ) break ; numCount [ key * i ] += M [ key ] ; } } 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 ) Console . WriteLine ( - 1 ) ; else { Console . WriteLine ( " LCM ▁ = ▁ " + lcm + " ▁ Length ▁ = ▁ " + length ) ; Console . Write ( " Indexes ▁ = ▁ " ) ; for ( int i = 0 ; i < n ; ++ i ) if ( lcm % arr [ i ] == 0 ) Console . Write ( i + " ▁ " ) ; } } public static void Main ( ) { int k = 14 ; int [ ] arr = { 2 , 3 , 4 , 5 } ; int n = arr . Length ; findSubsequence ( arr , n , k ) ; } }