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 ; Array in which sub sequence with size k with max GCD is to be found
function findMaxGCD ( arr , n , k ) { arr . sort ( function ( a , b ) { return a - b ; } ) ; let high = arr [ n - 1 ] ; let divisors = new Array ( high + 1 ) ; for ( let i = 0 ; i < divisors . length ; i ++ ) { divisors [ i ] = 0 ; } for ( let i = 0 ; i < n ; i ++ ) { for ( let j = 1 ; j <= Math . sqrt ( arr [ i ] ) ; j ++ ) { if ( arr [ i ] % j == 0 ) { divisors [ j ] ++ ; if ( j != Math . floor ( arr [ i ] / j ) ) divisors [ Math . floor ( arr [ i ] / j ) ] ++ ; } } } for ( let i = high ; i >= 1 ; i -- ) if ( divisors [ i ] >= k ) return i ; return 0 ; } let arr = [ 1 , 2 , 4 , 8 , 8 , 12 ] ; let k = 3 ; let n = arr . length ; document . write ( findMaxGCD ( arr , n , k ) ) ;