Find the GCD pair of the given group

Java Q&A: Finding GCD pairs of a given array is a common problem that requires calculation of the greatest common divisor (GCD) of the numbers in the array. In Java, you can use Euclidean algorithm to solve this problem. In this article, PHP editor Xigua will introduce how to use Java to write a method to find the GCD pair of a given array, helping readers better understand and apply this algorithm.

Question content

Given an integer array of size n, where n is an even number. Pick 2 numbers from the array and find gcd. Likewise, pick 2 items from the remaining items in the array and find gcd. Repeat the above steps to find the gcd pair. Sum the gcd values ​​and get the highest sum.

constraint:

n is in range 2 to 20
arr[i] is in range 1 to 10^9

Example 1:

arr = [3,4,9,5]

Answer:

4

illustrate:

a) gcd of (4,5) is 1
b) gcd of (3,9) is 3
sum = 1+3 = 4. this is the highest possible gcd sum.

Example 2:

arr = [1,2,3,4,5,6]

Answer:

6

illustrate:

a) gcd of (1,5) is 1
b) gcd of (2,4) is 2
c) gcd of (3,6) is 3
sum = 1+2+3 = 6. this is the highest possible gcd sum.

This is my code:

public static int solve(int[] ar) {
   int n = ar.length;
   Arrays.sort(ar);
   int sum = 0;
   for(int i=0; i<n/2; i++) {
     int a = ar.get(i), b = ar.get(n-i-1);
     int c = gcd(a,b); 
     sum += c;
   }
   return sum;
}

static int gcd(int a, int b)
{
    // if b=0, a is the GCD
    if (b == 0)
        return a;

    // call the gcd() method recursively by
    // replacing a with b and b with
    // modulus(a,b) as long as b != 0
    else
        return gcd(b, a % b);
}

My code works for the first example but gives wrong output for the second example. I debugged it and found that the method I was using was incorrect. What is the correct way to solve this problem?

Solution

We can recursively search all possible ways to calculate the total gcd. what to do?

If the array contains only two elements, we can only return the gcd of these two elements.

If it contains more, let's iterate over all value pairs. For each pair, we compute its gcd, and we also call our function recursively with a copy of the array with both values ​​removed. If we add the results of both calculations, we get the total gcd for the currently selected pair of values.

Now we just keep track of the best gcd found so far and return it at the end.

This is the code that (should) do exactly that.

int solve(int[] ar) {
  // if we have only two elements, there's not much else we can do.
  if(ar.length == 2) {
    return gcd(ar[0], ar[1]);
  }

  //keep track of the largest gcd
  int best = 0;
  
  // for every pair of values in the array
  //  make a copy of the array without the pair and call recursively
  for(int i = 0; i < ar.length; i++) {
    for(int j = i + 1; j < ar.length; j++) {
      
      int score = gcd(ar[i], ar[j]);
      
      // make a copy
      int[] ar2 = new int[ar.length - 2];
      int copy_k = 0;
      for(int k=0; k < ar.length; k++) {
        // skip values that we already visited
        if(k == i || k == j) {
          continue;
        }
        
        ar2[copy_k] = ar[k];
        copy_k += 1;
      }
      
      // call recursively
      score += solve(ar2);
      
      if(score > best) // we found a better pair
        best = score;
    }
  }
  
  return best;
}

This algorithm is quite slow. If you need to speed things up, there are at least two areas where you can improve:

• Computing gcd is an expensive operation. Precomputing the gcd of all possible pairs of unique values ​​and storing them in a hashmap will eliminate double calculations.
• It checks some possible permutations multiple times. (e.g. selecting the first pair and then the second pair on the next recursion is the same as selecting the second pair and then the first pair) I have some vague ideas on how to solve this problem, but it's too late tonight Yes, sorry.

Most likely there is a faster algorithm, this is just my idea.

Editor: Well, after some sleep, I suddenly understood. If we omit the outer loop when creating pairs, we won't get any duplicate sorting of pairs. Basically just replace i with 0 everywhere, like this:

for(int j = 1; j < ar.length; j++) {
    
  int score = gcd(ar[0], ar[j]);
  
  // Make a copy
  int[] ar2 = new int[ar.length - 2];
  int copy_k = 0;
  for(int k=1; k < ar.length; k++) {
    // Skip values that we already visited
    if(k == j) {
      continue;
    }
    
    ar2[copy_k] = ar[k];
    copy_k += 1;
  }
}

The above is the detailed content of Find the GCD pair of the given group. For more information, please follow other related articles on the PHP Chinese website!