Subsequence of size k with maximum possible GCD | Java 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 java . io . * ; import java . util . * ; class GFG { static int findMaxGCD ( int [ ] arr , int n , int k ) { Arrays . sort ( arr ) ; int high = arr [ n - 1 ] ; int [ ] divisors = new int [ high + 1 ] ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 1 ; j <= Math . sqrt ( arr [ i ] ) ; j ++ ) { if ( arr [ i ] % j == 0 ) { divisors [ j ] ++ ; if ( j != arr [ i ] / j ) divisors [ arr [ i ] / j ] ++ ; } } } for ( int i = high ; i >= 1 ; i -- ) if ( divisors [ i ] >= k ) return i ; return 0 ; } static public void main ( String [ ] args ) { int [ ] arr = { 1 , 2 , 4 , 8 , 8 , 12 } ; int k = 3 ; int n = arr . length ; System . out . println ( findMaxGCD ( arr , n , k ) ) ; } }