can anyone tell when will result of codevita round1 will publish?
In around 20 days…
Hetp ek question me help kroge…
Given an array find max value of GCD(a[i],a[j]) +j-i
Can you provide Problem link?
This reminds me of SUMAGCD from june long.
Nooo…it’s different
Yes I know, Just saying…
It will be better if you provide the constraints too, anyways I have O(N*log(n)) approach :
First map all the values of an error with their indexes in original array then run a loop for i from 2 to max/2 ( max is the highest value of an array) and generate all multiples of each no. And check if that multiple is present in map or not, if it is then do minindex= min( index of that multiple, mijindex) and maxindex =max(index of that multiple, maxindex) and that running every loop for i do ans =max(ans, I +maxindex - minindex).
I know explanation is not so good. So you can ping me anytime😝
1 Like
Here minindex is storing the index of first element which is the multiple of I wherease maxindex storing index of last multiple of I.
Explain with ex.
N less than 10 lakh
Let the array is 4 3 2 6 12
Indexed all element in map so
4-> 0
3 - >1
… So on
For(i=2; i<=6;i++) ( as gcd can’t be more than 6)
For(j=I ; j<=12 ; j+=I) ( this loop will generate all multiples of I till maximum element)
if( map[j] is present)
Found 4 so minindex =0
Then 6 maxindex is 3 now
8 is not present leave it
Got 12 maxindex becomes 4.
Maximum ans we can get for gcd=2 is 4-0+2 =6
Same loop run for every possible gcd means every number between 2 and 6. And you will get you answer
Answer of this example will 8 when gcd will be 4.
1 Like
So in general it can’t be more then 2nd largest element.?
Yes gcd will always be less than or equal to 2nd highest element as well as half of highest element.
1 Like
If array contains a=[10,10] then gcd=10 not 5(half of highest element)
Actually ab above only work if all element are distinct, if elements can be same first we need to use map of vector.
Can you give us the constraints?
N<10000000
A(i) < 10000
1 Like