HackerRank : Week of Code 34 – Maximum Gcd and Sum

By | July 19, 2017
Maximum Gcd and Sum: Hackerrank

Maximum Gcd and Sum : You are given two arrays  and  containing  elements each. Choose a pair of elements  such that:

  •  belongs to array .
  •  belongs to array .
  •  is the maximum of all pairs .

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.
NOTE:  returns the largest integer that divides both  and .
Input Format
The first line of the input contains  denoting the total number of elements of arrays  and . Next line contains n space separated positive integers denoting the elements of array . Next line contains n space separated positive integers denoting the elements of array .
Constraints
Output Format
From all the pairs having maximum , print the sum of one that has the maximum sum.

Sample Input 0

5
3 1 4 2 8
5 2 12 8 3

Sample Output 0

16

Explanation 0

Over all the pairs, if we choose  from array , and  from array , we get , which is the maximum gcd over all the pairs.

Thus, maximum sum of pair  is equal to