# Need help optimizing an algorithm that’s supposed to maximize the greatest common divisor of n elements by removing at most one element

Alright, first here’s the text of the problem:

You’re given n bags of candies where the i-th bag contains a[i] candies and all numbers a[i] are in the segment [1,m]. You can choose a natural number x and each second remove x candies from one of the bags if it contains at least x candies. The goal is to empty all the bags except at most one of them. Find the greatest possible value of x that allows you to achieve this goal.

The desired time complexity is O(n* log m);

What I managed(I think) to do is write an O(n^2 * log m) algorithm (the two nested for loops are O(n^2) and Euclid’s algorithm is O(log m)).

The code written in c++ is below. The second for loop calculates the gcd of the numbers excluding the i-th number and I calculate the maximum by considering all values of i, but apparently it can be done linearly. Any ideas on how to optimize it to O(n* log m)?

``int gcd(int a, int b){     if(b == 0)         return a;     return gcd(b, a%b); }   int greatestPossibleGcd(int *arr, int n){     int maxgcd = 0;     int current = 0;      for(int i=0;i<n;i++){         maxgcd = gcd(maxgcd, arr[i]);     }      for(int i=0;i<n;i++){         for(int j=0;j<n;j++){             if(j == i)                 continue;             current = gcd(current, arr[j]);         }         if(current > maxgcd)             maxgcd = current;          current = 0;     }      return maxgcd;  } ``
Posted on Categories proxies