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 ; Array in which pair with max GCD is to be found ; Size of array
def findMaxGCD ( arr , n ) : NEW_LINE INDENT high = 0 NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT high = max ( high , arr [ i ] ) NEW_LINE DEDENT count = [ 0 ] * ( high + 1 ) NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT count [ arr [ i ] ] += 1 NEW_LINE DEDENT counter = 0 NEW_LINE for i in range ( high , 0 , - 1 ) : NEW_LINE INDENT j = i NEW_LINE while ( j <= high ) : NEW_LINE INDENT if ( count [ j ] > 0 ) : NEW_LINE INDENT counter += count [ j ] NEW_LINE DEDENT j += i NEW_LINE if ( counter == 2 ) : NEW_LINE INDENT return i NEW_LINE DEDENT DEDENT counter = 0 NEW_LINE DEDENT DEDENT arr = [ 1 , 2 , 4 , 8 , 8 , 12 ] NEW_LINE n = len ( arr ) NEW_LINE print ( findMaxGCD ( arr , n ) ) NEW_LINE