Maximum Gcd and Sum

Question

You are given two arrays A and B containing n elements each. Choose a pair of elements (x, y) such that:
• x belongs to Array A
• y belongs to Array B
• GCD(x, y) is the maximum of all pairs (x, y).
If there is more than one such pair having maximum gcd, then choose the one with maximum sum. Print the sum of elements of this maximum-sum pair.

This is question from Hackerrank weekofcode 34.

from fractions import gcd

from itertools import product
n = int(input().strip()) #two arrays of equal length
A = set(map(int, input().strip().split(' '))) #array1
B = set(map(int, input().strip().split(' '))) # arry2
output_sum=[]
output_GCD=[]
c=list(product(A,B))
for i in c:

    temp1=i[0]
    temp2=i[1]

    sum_two=temp1+temp2

    temp3=gcd(temp1,temp2)
    output_GCD.append(temp3)
    output_sum.append(temp1+temp2)
temp=[]
for i in range(len(output_GCD)):
  if(output_GCD[i]==max(output_GCD)):
    temp.append(output_sum[i])
print(max(temp))

This solution works for smaller conditions and I got timed out for most of the test cases, please help me how to improve my solution.

user_6176563 · Answer

You must convert A and B to Set(to easily find in it)

def maximumGcdAndSum(A, B):
    A = set(A)
    B = set(B)
    max_nbr = max(max(A), max(B))
    i = max_nbr

    while i > 0:  # for each i starting from max number
        i_pow = i  # i, i^2, i^3, i^4, ...
        maxa = maxb = 0

        while i_pow <= max_nbr:  # '<=' is a must here
            if i_pow in A:
                maxa = i_pow  # get the max from power list which devides A
            if i_pow in B:
                maxb = i_pow  # get the max from power list which devides B
            i_pow += i
        if maxa and maxb:
            return maxa + maxb  # if both found, stop algorithm
        i -= 1

    return 0

Maximum Gcd and Sum

2 Answers