Find the greatest gcd among the pairs of two equal sized arrays and prints the sum of that pair

Question

You are given two arrays AA and BB containing elements each. Choose a pair of elements x,y such that:

x belongs to array AA. y belongs to array BB. gcd(x,y) is the maximum for 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: returns gcd(x,y) the largest integer that divides both x and y.

Constraints:

$$1≤N≤5\cdot 10^5$$ $$1≤A_i≤10^6$$ $$1≤B_i≤10^6$$

Input format:

The first line of the input contains n denoting the total number of elements of arrays AA and BB. Next line contains n space separated positive integers denoting the elements of array AA. Next line contains n space separated positive integers denoting the elements of array BB.

Output format:

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

public class Solution2 {

static int gcdcalc(int x, int y){
   if(y == 0)
   {
       return x; 
   }
   return gcdcalc(y, x%y);
}


static int maximumGcdAndSum(int[] A, int[] B) {
    int gcd,sum,maxgcd=0,maxsum=0;
    for(int A_i = 0; A_i < A.length; A_i++)
    {
        for(int B_i = 0; B_i < B.length; B_i++)
        {
            sum = A[A_i] + B[B_i];
            gcd = gcdcalc(A[A_i], B[B_i]);
            if(maxgcd < gcd)
            {
                maxgcd = gcd;
                maxsum = sum;
            }
            if(maxgcd == gcd)
            {
                if(maxsum < sum)
                    maxsum = sum;
            }
        }
    }
    return maxsum;
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int[] A = new int[n];
    for(int A_i = 0; A_i < n; A_i++){
        A[A_i] = in.nextInt();
    }
    int[] B = new int[n];
    for(int B_i = 0; B_i < n; B_i++){
        B[B_i] = in.nextInt();
    }
    int res = maximumGcdAndSum(A, B);
    System.out.println(res);
 }
}

Answer 1

    int gcd,sum,maxgcd=0,maxsum=0;

You don't need to declare gcd and sum yet.

    int maxGcd = 0;
    int maxSum = 0;

It's also generally better not to initialize more than one variable per line. It's not a functional difference. It's a readability thing.

The Java standard is to capitalize the second and later words.

            sum = A[A_i] + B[B_i];
            gcd = gcdcalc(A[A_i], B[B_i]);

This could be

            int sum = A[A_i] + B[B_i];
            int gcd = gcdcalc(A[A_i], B[B_i]);

You don't use these outside the current iteration. So you can declare and initialize them at the same time.

            if(maxgcd == gcd)
            {
                if(maxsum < sum)
                    maxsum = sum;

This could be

            else if (maxgcd == gcd && maxsum < sum)
            {
                maxsum = sum;

If the maxgcd is less than gcd, then they won't be equal. So we don't need to check both. The else makes it so that we only check for equality if not less than.

You don't need two if statements. One statement with two clauses is sufficient. Due to the way that short circuit comparisons work, this will be the same efficiency as the original code.

I prefer to have a space between the if and the (. I find it easier to see that it is an if and not a method call that way.

I would encourage you to add more vertical whitespace. Again, I find breaking up the statements into logical groups makes it easier to read.

   if(y == 0)
   {
       return x; 
   }
   return gcdcalc(y, x%y);

This could be just

   return (y == 0) ? x : gcdcalc(y, x%y);

Same efficiency, just a bit terser.

If you find yourself trying to wring out every bit of efficiency, there is an iterative version of this that is probably faster.

Answer 2

Instead of using two int[]s, you could use two HashSet<Integer> instances instead, because duplicates in any of the two arrays can be ignored. Also, the declaration of gcd and sum in maximumGcdAndSum(int[], int[]) could be moved into the innermost for loop to reduce their scope to the smallest extent necessary, which would make the code a bit clearer in my opinion. Other than that, your code seems to be succinct and working.