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}
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
I think this article might help a little bit- Find pair with maximum GCD in an array - GeeksforGeeks
same doubt i too have, is Euclid’s algorithm a better option ? my solution for problem RECIPE Problem - CodeChef is which uses euclid’s to find gcd
CodeChef: Practical coding for everyone
is this good approach or any other efficient way ?
This looked familiar, so I googled it:
Updated with constraints.
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).
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:
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.