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; } `