Pair with maximum GCD 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 .
< ? php function gcdMax ( $ a , $ b , $ n , $ N ) { $ cnt = array_fill ( 0 , $ N , 0 ) ; $ first = array_fill ( 0 , $ N , 0 ) ; $ second = array_fill ( 0 , $ N , 0 ) ; for ( $ i = 0 ; $ i < $ n ; ++ $ i ) $ cnt [ $ a [ $ i ] ] = 1 ; for ( $ i = 1 ; $ i < $ N ; ++ $ i ) for ( $ j = $ i ; $ j < $ N ; $ j += $ i ) if ( $ cnt [ $ j ] ) $ first [ $ i ] = max ( $ first [ $ i ] , $ j ) ; $ cnt = array_fill ( 0 , $ N , 0 ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ cnt [ $ b [ $ i ] ] = 1 ; for ( $ i = 1 ; $ i < $ N ; $ i ++ ) for ( $ j = $ i ; $ j < $ N ; $ j += $ i ) if ( $ cnt [ $ j ] ) $ second [ $ i ] = max ( $ second [ $ i ] , $ j ) ; $ x = $ N - 1 ; for ( ; $ x >= 0 ; $ x -- ) if ( $ first [ $ x ] && $ second [ $ x ] ) break ; echo $ first [ $ x ] . " ▁ " . $ second [ $ x ] . " STRNEWLINE " ; } $ a = array ( 3 , 1 , 4 , 2 , 8 ) ; $ b = array ( 5 , 2 , 12 , 8 , 3 ) ; $ n = sizeof ( $ a ) ; $ N = 20 ; gcdMax ( $ a , $ b , $ n , $ N ) ; ? >