Find pair with maximum GCD in an array | Java Code to Find pair with maximum GCD in an array ; function to find GCD of pair with max GCD in the array ; Calculating MAX in array ; Maintaining count array ; Variable to store the multiples of a number ; Iterating from MAX to 1 GCD is always between MAX and 1 The first GCD found will be the highest as we are decrementing the potential GCD ; Iterating from current potential GCD till it is less than MAX ; A multiple found ; Incrementing potential GCD by itself To check i , 2 i , 3 i ... . ; 2 multiples found , max GCD found ; Driver program to test above function ; Array in which pair with max GCD is to be found ; Size of array
class GFG { public static int findMaxGCD ( int arr [ ] , int n ) { int high = 0 ; for ( int i = 0 ; i < n ; i ++ ) high = Math . max ( high , arr [ i ] ) ; int count [ ] = new int [ high + 1 ] ; for ( int i = 0 ; i < n ; i ++ ) count [ arr [ i ] ] ++ ; int counter = 0 ; for ( int i = high ; i >= 1 ; i -- ) { int j = i ; while ( j <= high ) { if ( count [ j ] > 0 ) counter += count [ j ] ; j += i ; if ( counter == 2 ) return i ; } counter = 0 ; } return 1 ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 2 , 4 , 8 , 8 , 12 } ; int n = arr . length ; System . out . println ( findMaxGCD ( arr , n ) ) ; } }