Pair with maximum GCD from two arrays | CPP 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 program to test the above function ; Maximum possible value of elements in both arrays .
#include <bits/stdc++.h> NEW_LINE using namespace std ; void gcdMax ( int a [ ] , int b [ ] , int n , int N ) { int cnt [ N ] = { 0 } ; int first [ N ] = { 0 } , second [ N ] = { 0 } ; 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 ] ) first [ i ] = max ( first [ i ] , j ) ; memset ( cnt , 0 , sizeof ( cnt ) ) ; for ( int i = 0 ; i < n ; ++ i ) cnt [ b [ i ] ] = true ; for ( int i = 1 ; i < N ; ++ i ) for ( int j = i ; j < N ; j += i ) if ( cnt [ j ] ) second [ i ] = max ( second [ i ] , j ) ; int i ; for ( i = N - 1 ; i >= 0 ; i -- ) if ( first [ i ] && second [ i ] ) break ; cout << " Maximum ▁ GCD ▁ pair ▁ with ▁ maximum ▁ " " sum ▁ is ▁ " << first [ i ] << " ▁ " << second [ i ] << endl ; } int main ( ) { int a [ ] = { 3 , 1 , 4 , 2 , 8 } ; int b [ ] = { 5 , 2 , 12 , 8 , 3 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int N = 20 ; gcdMax ( a , b , n , N ) ; return 0 ; }