Find the longest subsequence of an array having LCM at most K | Python3 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
from collections import defaultdict NEW_LINE def findSubsequence ( arr , n , k ) : NEW_LINE INDENT M = defaultdict ( lambda : 0 ) NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT M [ arr [ i ] ] += 1 NEW_LINE DEDENT numCount = [ 0 ] * ( k + 1 ) NEW_LINE for p in M : NEW_LINE INDENT if p <= k : NEW_LINE INDENT i = 1 NEW_LINE while p * i <= k : NEW_LINE INDENT numCount [ p * i ] += M [ p ] NEW_LINE i += 1 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT lcm , length = 0 , 0 NEW_LINE for i in range ( 1 , k + 1 ) : NEW_LINE INDENT if numCount [ i ] > length : NEW_LINE INDENT length = numCount [ i ] NEW_LINE lcm = i NEW_LINE DEDENT DEDENT if lcm == 0 : NEW_LINE INDENT print ( - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " LCM ▁ = ▁ { 0 } , ▁ Length ▁ = ▁ { 1 } " . format ( lcm , length ) ) NEW_LINE print ( " Indexes ▁ = ▁ " , end = " " ) NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT if lcm % arr [ i ] == 0 : NEW_LINE INDENT print ( i , end = " ▁ " ) NEW_LINE DEDENT DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT k = 14 NEW_LINE arr = [ 2 , 3 , 4 , 5 ] NEW_LINE n = len ( arr ) NEW_LINE findSubsequence ( arr , n , k ) NEW_LINE DEDENT