Pair with maximum GCD from two arrays | Java program to find maximum GCD pair from two arrays ; Find the maximum GCD pair with maximum sum ; array to keep a count of existing elements ; first [ i ] and second [ i ] are going to store maximum multiples of i in a [ ] and b [ ] respectively . ; traverse through the first array to mark the elements in cnt ; Find maximum multiple of every number in first array ; Find maximum multiple of every number in second array . We re - initialise cnt [ ] and traverse through the second array to mark the elements in cnt ; if the multiple is present in the second array then store the max of number or the pre - existing element ; traverse for every elements and checks the maximum N that is present in both the arrays ; Driver Code ; Maximum possible value of elements in both arrays .
class GFG { static void gcdMax ( int [ ] a , int [ ] b , int n , int N ) { int [ ] cnt = new int [ N ] ; int [ ] first = new int [ N ] ; int [ ] second = new int [ N ] ; for ( int i = 0 ; i < n ; ++ i ) cnt [ a [ i ] ] = 1 ; for ( int i = 1 ; i < N ; ++ i ) for ( int j = i ; j < N ; j += i ) if ( cnt [ j ] > 0 ) first [ i ] = Math . max ( first [ i ] , j ) ; cnt = new int [ N ] ; for ( int i = 0 ; i < n ; ++ i ) cnt [ b [ i ] ] = 1 ; for ( int i = 1 ; i < N ; ++ i ) for ( int j = i ; j < N ; j += i ) if ( cnt [ j ] > 0 ) second [ i ] = Math . max ( second [ i ] , j ) ; int x ; for ( x = N - 1 ; x >= 0 ; x -- ) if ( first [ x ] > 0 && second [ x ] > 0 ) break ; System . out . println ( first [ x ] + " ▁ " + second [ x ] ) ; } public static void main ( String [ ] args ) { int [ ] a = { 3 , 1 , 4 , 2 , 8 } ; int [ ] b = { 5 , 2 , 12 , 8 , 3 } ; int n = a . length ; int N = 20 ; gcdMax ( a , b , n , N ) ; } }