2
\$\begingroup\$

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;
}
\$\endgroup\$
9
  • \$\begingroup\$ (If you sort (see JS1's answer (or get sorted input), you could get smart and disregard values no greater than the current max GCD. If numbers of interesting values are dissimilar, it might prove advantageous looping over the "longer array" in the inner loop.) \$\endgroup\$
    – greybeard
    Jul 20, 2017 at 18:36
  • \$\begingroup\$ Come to think of it, if one array is considerably smaller than the other, it may be worth excluding elements that are true divisors of at least one other. \$\endgroup\$
    – greybeard
    Jul 20, 2017 at 18:47
  • \$\begingroup\$ @greybeard can u Type code for that. I am new to java too. \$\endgroup\$ Jul 20, 2017 at 18:48
  • \$\begingroup\$ (I should be able to, but, just a mo': I'm searching for "real algorithmic/math insights" on SO) \$\endgroup\$
    – greybeard
    Jul 20, 2017 at 18:54
  • \$\begingroup\$ Oh, look, it may be a current contest problem: can you please help us verify this is not the case here? (Most helpful Q&As I found) \$\endgroup\$
    – greybeard
    Jul 20, 2017 at 19:26

1 Answer 1

2
\$\begingroup\$

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.

\$\endgroup\$
8
  • \$\begingroup\$ I was thinking you gonna Make some magic in the Algorithm but u just removed some bugs. \$\endgroup\$ Jul 20, 2017 at 17:39
  • 1
    \$\begingroup\$ @RishabhDeepSingh I'm not sure what magic you expected because given the problem you described, what you did was pretty much the only way to do it. Also, I would think that making the code work correctly would be more important than making it work faster. \$\endgroup\$
    – JS1
    Jul 20, 2017 at 18:10
  • \$\begingroup\$ I was working on a Competitive programming problem so I want it to work faster as it works correctly. \$\endgroup\$ Jul 20, 2017 at 18:28
  • \$\begingroup\$ (for terseness, if nothing else, I prefer for (int i = length ; 0 <= --i ; ) (just for counting, I don't trust memory hierarchies to be as fast indexing down)) \$\endgroup\$
    – greybeard
    Jul 20, 2017 at 18:30
  • \$\begingroup\$ @RishabhDeepSingh Perhaps you should present the entire programming problem. Maybe there is some step that can simplify the problem, unless that problem is exactly as you have stated. Also, you didn't present your code for the GCD function. \$\endgroup\$
    – JS1
    Jul 20, 2017 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.