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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findSubsequence ( int * arr , int n , int k ) { map < int , int > M ; for ( int i = 0 ; i < n ; ++ i ) ++ M [ arr [ i ] ] ; int * numCount = new int [ k + 1 ] ; for ( int i = 0 ; i <= k ; ++ i ) numCount [ i ] = 0 ; for ( auto p : M ) { if ( p . first <= k ) { for ( int i = 1 ; ; ++ i ) { if ( p . first * i > k ) break ; numCount [ p . first * i ] += p . second ; } } 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 ) cout << -1 << endl ; else { cout << " LCM ▁ = ▁ " << lcm << " , ▁ Length ▁ = ▁ " << length << endl ; cout << " Indexes ▁ = ▁ " ; for ( int i = 0 ; i < n ; ++ i ) if ( lcm % arr [ i ] == 0 ) cout << i << " ▁ " ; } } int main ( ) { int k = 14 ; int arr [ ] = { 2 , 3 , 4 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; findSubsequence ( arr , n , k ) ; return 0 ; }