 # How to solve this GCD problem efficiently?

Given an array of positive integers A, let i and j be some indices on this array. Find the maximum value of gcd(A[j], A[i]) + j - i. Where `gcd` denotes the Greatest Common Divisor.

Edit:
Constraints are:
1 <= length(A) <= 10^{5}
1 <= A[i] <= 10^{5}

2 Likes

No limits, therefore I propose O(N ^2 * logAi) gg ez solution

I think, what we can do is, take an array to count the divisors divisors of every element of the array. The counting of divisors will take O(sqrt(arr[i])). Now just loop from last index to first index(index 1) and if we found an index >1, that means it is divisor of two elements and also the max GCD and just store the positions.
Complexity- O(N*sqrt(arr[i]))

How in O(N ^ {2})? Even with the Brute Force solution it will be O(N^{2}.log_{2}K) where K is the maximum number in the array, you probably missed accounting for the GCD part, I anyway need a better solution than this.

Then at least provide some limits so we have grounds to work with

Sorry, but lost you on this part.

Traverse the frequency array from last index to 1. Now suppose, in the array any elements is greater than 1. That means, it is a common factor of more than 1 elements, or to simply say, it is the divisor of 2 elements, which in also the case means, it is the max GCD of two pairs in the array.

May be I am still not getting you but based on what I interpreted from your comment, what if none of the element is a factor of other. Consider the case-
`8, 12, 35, 49`

same doubt i too have, is Euclid’s algorithm a better option ? my solution for problem https://www.codechef.com/problems/RECIPE is which uses euclid’s to find gcd
https://www.codechef.com/viewsolution/27527238
is this good approach or any other efficient way ?

This looked familiar, so I googled it:

2 Likes

Updated with constraints.

1 Like

Cool, for each number find all of its divisors. For each divisor find the max indice of a number dividing by it, and the min indice too. This is in total O(MAX * logMAX).

2 Likes

This is the question from infitq round 2 August…

Here is how I would approach the problem.

Step 1: What are the possible divisors of A[i] given that they are of range 1 to 10^5. Only 10^5 possibilities, a number we can work with!
Step 2: For every element can we find all its divisors? Yes. This is a O(rootN) algo per element.
Step 3: For every divisor can we record its first occurence and last occurence in array? Yes.

From Step 2 and 3 we get 2 maps:

1. Map 1 -> Divisors and Frequency
2. Map 2 -> Divisors and pair(first occurence, last occurence).

Determine the largest gap between last occurence and first occurence. Lets call it gapMax. Similarly get the largest divisor. lets called gcdMAX. Lets get a third variable called Max which is max(gapMax, gcdMax). Final answer cannot be larger than Max.

Step 3. Go through Map 1 -> For each divisor greater than Max, get the last occurence - first occurence. Add it to GCD, if this value is greater than Max, this is the new Max.