We can use dynamic programming to solve this problem. The states will be as follows-
base case is if there is only one element -
dp[0][0]=ar[0];
dp[0][1]=ar[0]+1;
dp[0][2]=ar[0]-1;
dp[i][0] -> means im taking ar[i] as my current number and storing the max gcd possible from previously stored results , i.e, the transition will be
dp[i][0]=max({__gcd(ar[i],dp[i-1][0]),__gcd(ar[i],dp[i-1][1]),__gcd(ar[i],dp[i-1][2])});
Similary ,
dp[i][1] -> means im taking ar[i]+1 as my current number and storing the max gcd possible from previously stored results, i.e, the transition will be
dp[i][1]=max({__gcd(ar[i]+1,dp[i-1][0]),__gcd(ar[i]+1,dp[i-1][1]),__gcd(ar[i]+1 ,dp[i-1][2])});
similarly,
dp[i][2]-> means im taking ar[i]-1 as my current number and storing the max gcd possible from previously stored results, i.e, the transition will be
dp[i][2]=max({__gcd(ar[i]-1,dp[i-1][0]),__gcd(ar[i]-1,dp[i-1][1]),__gcd(ar[i]-1,dp[i-1][2])});
thus our final ans will be ->
ans=max({3ll,dp[n-1][0],dp[n-1][1],dp[n-1][2]});
here 3 is taken bcz i can get a minimium gcd of 3 for any array.
Interesting! Can you please share your code?
I take a cartesian product, all combinations of numbers in the current set and 3 possible values of next element.
But approach suggested by kck_rocks below is much better.
In any case, your approach should also not give WA unless there is some implementation bug.
I dont know …there is no implementation bug…BTW thanks for your speedy response
https://www.codechef.com/viewsolution/42870637-This is my code
It is not commented… 
I hope you can find the bug in my code
Here is my code
#include<bits/stdc++.h>
using namespace std;
bool all_ok(int x,int arr[],int n)
{
for(int j=1;j<n;j++)
{
if((arr[j]%x)==0 || (arr[j]%x==1) || (arr[j]+1)%x==0)
continue;
else
return false;
}
return true;
}
int find_gcd(int g,int arr[],int n)
{
int ans=1;
for(int i=1;i*i<=g;i++)
{
if(g%i==0)
{
if(all_ok(i,arr,n))
{
ans=max(ans,i);
}
if(all_ok(g/i,arr,n));
{
ans=max(ans,g/i);
}
}
}
return ans;
}
int main()
{
int t;
cin>>t;
while(t)
{
int n;
cin>>n;
int arr[n];
for(auto &x:arr)
{
cin>>x;
}
sort(arr,arr+n);
int ans=find_gcd(arr[0],arr,n);
ans=max(ans,find_gcd(arr[0]+1,arr,n));
ans=max(ans,find_gcd(arr[0]-1,arr,n));
cout<<ans<<endl;
t–;
}
}
Unfortunately they are not allowing me to share my submission link…Hope you can find out my bug —>kindly follow the steps I mentioned…you will be able to grasp my approach
Then after that how do you decide which is your final ans…?
Good debugging question
Remove the semicolon after if
https://www.codechef.com/viewsolution/42872993
This is what our team did. We considered the max of gcd(m,a[i]) , gcd(m,a[i]+1), gcd(m,a[i]-1) , max of gcd(m+1,a[i]), gcd(m+1,a[i]+1), gcd(m+1,a[i]-1) and max of gcd(m-1,a[i]),gcd(m-1,a[i]+1),gcd(m-1,a[i]-1) separately, where m is the minimum element in the array. We consider the min of each of these max values separately, as i varies from 0 to n-1. And finally, the answer is the maximum of the original gcd and these three values obtained.
Thanks , …
Can someone pls tell what’s wrong with our solution for the Boars of Armorica ?CodeChef: Practical coding for everyone. Tried doing with bitmask DP.
I think there is some bug in your implementation.
My team followed the same logic and got AC
Ya , cubercoder Sir has pointed it out
was this code accepted? If yes, can you share the link to the code
Can you tell me that why is taking 3 explicitly necessary , like why isnt dp itself knowing that answer cant be less than 3 , my solution in which I didnt wrote the condition of 3 gave me a Wrong Answer . Whereas the solution containing 3 gave me a right answer . Moreover can I have a Test Case where we need 3 to be the lower limit.
You can have mine it is implemented with the same logic the only difference is that ans[i][0] is a[i]-1, ans[i][1] is a[i], ans[i][2] is a[i]+1
https://www.codechef.com/viewsolution/42876751
Okay thanks
The gcd will always be the factor of the smallest number of the array.
Let the smallest no. be X. So X-1,X,X+1 will be only three possibilities we have to consider,so find out all the factors of these three no. and sort then in dec. order.
Now we just have to check which of these factor can divide all the no. of the given array.To do this for each A[i] we have three possibilities (A[i]-1,A[i],A[i]+1) just check if the any of these three no. is a multiple of that
no. or not.
My code:CodeChef: Practical coding for everyone