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

• Zeta: "Admittedly, this is a duplicate of this question". No, it isn't. Don't worry about it. Yours is in Python, theirs is in C++. Make sure to include enough information in your own question, the other might get deleted at some point since it's off-topic for this site.
• Peilonrayz: I have concern with two of your sentences: "it has successfully passed some of the test cases." If it doesn't pass all the test cases, then this is unfortunately off-topic. Also "But it does throw runtime exceptions", are these intended? It doesn't, to me, look like it should. And so you may want to re-phrase the sentence, if it does work as intended.
• lightsong: @Peilonrayz I feel it's logically correct and that's what I've tried to better. But the website that accepts my code and runs it against their test cases masks the test cases. So all I see is the reason the code failed against them - which is listed as a runtime exception - that's what I meant when I said that. It passes for my test case on my local machine. I guess what I'm looking for is for someone to tell me if there's some obvious error that I'm making in terms of array handling or something of the sort and also if this is the most optimized way of writing this code.
• Peilonrayz: I've requested this question be re-opened on Meta.

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.

• Peilonrayz: I don't think test_halfmillion_elements_different works as you expect, :) Heck who'd think A = islice(count(), 100); list(product(A, A)) is an empty array...

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