Subsequence of size k with maximum possible GCD | Python 3 program to find subsequence of size k with maximum possible GCD . ; function to find GCD of sub sequence of size k with max GCD in the array ; Computing highest element ; Array to store the count of divisors i . e . Potential GCDs ; Iterating over every element ; Calculating all the divisors ; Divisor found ; Incrementing count for divisor ; Element / divisor is also a divisor Checking if both divisors are not same ; Checking the highest potential GCD ; If this divisor can divide at least k numbers , it is a GCD of at least one sub sequence of size k ; Driver code ; Array in which sub sequence with size k with max GCD is to be found
import math NEW_LINE def findMaxGCD ( arr , n , k ) : NEW_LINE INDENT high = max ( arr ) NEW_LINE divisors = [ 0 ] * ( high + 1 ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( 1 , int ( math . sqrt ( arr [ i ] ) ) + 1 ) : NEW_LINE INDENT if ( arr [ i ] % j == 0 ) : NEW_LINE INDENT divisors [ j ] += 1 NEW_LINE if ( j != arr [ i ] // j ) : NEW_LINE INDENT divisors [ arr [ i ] // j ] += 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT for i in range ( high , 0 , - 1 ) : NEW_LINE INDENT if ( divisors [ i ] >= k ) : NEW_LINE INDENT return i NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 2 , 4 , 8 , 8 , 12 ] NEW_LINE k = 3 NEW_LINE n = len ( arr ) NEW_LINE print ( findMaxGCD ( arr , n , k ) ) NEW_LINE DEDENT