Maximizing GCD of two arrays of numbers

Question

I am new to coding. Given int arrays A and B, I would like to find the maximum GCD (Greatest Common divisor) any element of A and any element of B. I am doing the following

1. Sorting both arrays, then
2. Comparing every value of array A to array B to find GCD
3. Using a temp number I am checking if the GCD found is bigger than previous.
4. Finally returning the value (i.e. temp)

The GCD(a,b) returns the Greatest Common divisor of a and b.

Note: I am not comparing elements of A array with A.

Is there any way to improve the performance of my Code?

I want to decrease the time for a large number of inputs of Arrays A and B in the for loops by applying some Conditions.

Example :

A=2,5,8,9

B=4,12,8,7,16

Now if we choose 8 from A and 8 from B we get maximum GCD i.e. 8 . And then returning The maximum GCD (i.e. 8 in my example).

   private static int GCD(int a, int b) {
    BigInteger b1 = BigInteger.valueOf(a);
    BigInteger b2 = BigInteger.valueOf(b);
    BigInteger gcd = b1.gcd(b2);
    return gcd.intValue();
    }

 public static int maximumGcd(int[] A, int[] B) {
    Arrays.sort(A);
    Arrays.sort(B);
    int temp = 0;
    for (int i = A.length-1; i >0; i--) {
        for (int j = A.length-1; j >0; j--) {
            int tempGcd = GCD(A[i],B[j]);
            if ( tempGcd > temp){
                temp = tempGcd;
            }
        }
    }
    return temp;
}

Answer 1

Bug: off by one

In both your loops, you fail to loop to index 0. For example, if the length of array A is 5, then your loop:

for (int i = A.length-1; i >0; i--) {

will cover indices 4,3,2,1 and then stop. It should be written like this in order to also loop to index 0:

for (int i = A.length-1; i >= 0; i--) {

Bug: array out of bounds error

You made a copy and paste error here:

    for (int j = A.length-1; j >0; j--) {

This should have been:

    for (int j = B.length-1; j >= 0; j--) {

In other words, you used the length of A where you should have used the length of B. Thus, if array A is bigger than array B, you would index past the end of array B and get an out of bounds error.

Useless statements

Your code contains a few useless statements:

Arrays.sort(A);
Arrays.sort(B);
int sumMax = A[0]+B[0];

There is no need to sort the arrays since the order in which you loop through the arrays doesn't matter. The sumMax variable is never used after it is initialized.

Better algorithm

I suspect this may be a current programming challenge so I won't write any code or go into too much detail here.

The current solution is \$O(N*M)\$ where \$N\$ and \$M\$ are the sizes of the arrays. Instead of comparing one number with one number, if you could compare one number to a whole array, you could reduce your complexity by a lot.

How could you do this? Suppose for one whole array, you compute and remember all the possible divisors for each number in that array. Then if you go through the other array, you can compute the divisors for each number and see if each divisor appeared in the first array. If it did, then you have found a possible GCD for an A/B pair. If you can ensure that your divisor lookup is \$O(1)\$, then your total complexity should be:

\$O(N*F(N) + M*F(M))\$ where \$F(N)\$ is the amount of time it takes to factor a number (i.e. find its divisors). The normal way to factor a number would take \$O(\sqrt N)\$ time, but there may be faster ways of doing it, especially if the number range is limited.