Sum of Maximum GCD from two arrays

Question

I've written a program to solve the same problem as Sum of Maximum GCD.

My solution contains working code and it has successfully passed some of the test cases. But it does throw runtime exceptions and I'm trying to understand where I could be going wrong. I don't see any segmentation faults that could be tripping it up.

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 \$x, y\$ having maximum \$\gcd\$, then choose the one with maximum sum. Print the sum of elements of this maximum-sum pair.

NOTE: \$\gcd(x,y)\$ the largest integer that divides both \$x\$ and \$y\$.

Constraints:

• \$1 \le N \le 5 \times 10^5\$
• \$1 \le A_i \le 10^6\$
• \$1 \le B_i \le 10^6\$

Input Format

The first line of the input contains n denoting the total number of elements of arrays \$A\$ and \$B\$. Next line contains \$n\$ space separated positive integers denoting the elements of array \$A\$. Next line contains \$n\$ space separated positive integers denoting the elements of array \$B\$.

Output Format

From all the pairs having maximum gcd, print the sum of one that has the maximum sum.

---

I'm still actively trying to find the issue, though I think I could benefit from unbiased eyes and criticism to help me better my code.

#!/bin/python3

import sys
import itertools
import math
def maximumGcdAndSum(A, B):
    C = []
    C.append(A)
    C.append(B)
    D=[]
    E=[]
    gcds=[1]
    sums=[]
    prodC = itertools.product(*C)
    for element in prodC:
        gcdVal = math.gcd(element[0],element[1])
        D.append((gcdVal,sum(element)))
        gcds.append(gcdVal)
       # sums.append(sum(element))
   # print(D)
    maxGCD = max(gcds)
    sumsL = [1]
#print(gcds)
   # print(sums)
    for i in D:
        if i[0] == maxGCD:
            sumsL.append(i[1])
    return max(sumsL)
    # Complete this function

if __name__ == "__main__":
    n = int(input().strip())
    A = list(map(int, input().strip().split(' ')))
    B = list(map(int, input().strip().split(' ')))
    res = maximumGcdAndSum(A, B)
    print(res)

Sample input tried -

5
3 1 4 2 8
5 2 12 8 3

Output Expected -

16

Output Obtained -

16

Answer 1

There are quite a few ways to reduce the number of lines in your program, and improve the readability of your program:

• If you want to return a certain number when A and B are empty, use a guard clause.

  Personally I'd default to -1, rather than 1.

• When building a list, you can use C = [A, B], rather than appending.

• You don't need to build an array, to unpack it into a function. itertools.product(A, B) is fine.
• The list gcds is the same as the first index of D. It'd be simpler if you just used D.
• The lists E and sums are unused, and so should be removed.
• The 'comments', commented out code, is generally unhelpful and distract from the algorithm. I'd recomend removing them.
• Rather than building a list with D = [] for i in ...: d.append(i), you can use a list comprehension.
• Rather than building a list that may take ~2275GB of RAM, you may instead want to use a generator / generator comprehension.
• max works on a list of tuples.

And so I'd rather use:

import itertools
import math

def maximumGcdAndSum(A, B):
    if not (a or b):
        return -1
    nums = (
        (math.gcd(a, b), a + b)
        for a, b in itertools.product(A, B)
    )
    return max(nums)[1]

if __name__ == "__main__":
    n = int(input().strip())
    A = list(map(int, input().strip().split(' ')))
    B = list(map(int, input().strip().split(' ')))
    res = maximumGcdAndSum(A, B)
    print(res)

This however is likely to still produce a time limit exceeded error. I'm thinking of a better algorithm.

Answer 2

Tests should reflect the specification

The limits on the input are

• 1 ≤ N ≤ 500,000
• 1 ≤ A[i] ≤ 1,000,000 ∀ i
• 1 ≤ B[i] ≤ 1,000,000 ∀ i

I see no tests for any of the extreme cases.

It's quite easy to test the small cases, using fixed arrays. The easiest way to test is to use Python's unittest module:

if __name__ == "__main__":
    import unittest

    class TestGcdSum(unittest.TestCase):
        def test_one_element(self):
            self.assertEqual(maximumGcdAndSum([1], [1]), 2)

        def test_two_elements_equal_gcd(self):
            self.assertEqual(maximumGcdAndSum([1,2], [3,7]), 9) # 2 + 7

        def test_two_elements_different_gcd(self):
            self.assertEqual(maximumGcdAndSum([64,1000000], [625, 1000000]), 2000000)

    unittest.main()

We still haven't yet tested the upper limit of N, namely half a million elements in each of A and B. We can easily add another test:

        def test_halfmillion_elements_different(self):
            A = range(1, 500001)
            self.assertEqual(maximumGcdAndSum(A, A), 1000000)

I recommend setting execution limits (e.g. ulimit -v 1048576 to give yourself a reasonably generous 1GB of virtual memory) before running this test, as it exposes the memory consumption of the program.

It's now time to improve the test program to avoid that limit.

Answer 3

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