# Help needed in Maximum GCD (CP Potpourri)

My solution is accepted, but this is obviously wrong solution.
It fails on the test case-

1
3
11 7 6


My output- 3
Expected output - 4

Here is my code-

Code
#include<bits/stdc++.h>
using namespace std;

int fun(int elem, int res){
int ans = __gcd(elem, res);
ans = max(ans,__gcd(elem, res - 1));
ans = max(ans,__gcd(elem, res + 1));
return ans;
}
int maxGCD(int A[] , int N)
{
int x = A;
int y = A + 1;
int z = A - 1;

for(int i = 1; i < N; i++){
x = fun(x, A[i]);
y = fun(y, A[i]);
z = fun(z, A[i]);
}
int mx = max({3, x, y, z});
return mx;
}

int main()
{
int T;
cin>>T;
while(T--){
int N;
cin>>N;
int A[N];
for(int i = 0; i < N; i++){
cin >>A[i];
}
cout << maxGCD(A, N) << "\n";
}
}


Can someone please tell, what changes do I need to make in my code or is it simply that greedy fails?

This Greedy Fails according to me. You can’t make it work after making slight fixes in this code.

So any greedy fails right?

No, this greedy strategy fails doesn’t imply all greedy strategies should fail.

Oh. Can you please brief a greedy solution as all the greedy discussed here fails

This is the approach that I can prove to be correct.

• So firstly sort the entire array and consider the smallest element - A_1.
Hence what we can be assured of is that our answer would be one of the factors of A_1,A_1+1,A_1-1.
• Now factorise A_1,A_1+1,A_1-1 and push all the factors into one HashSet say B. Now all the elements of the HashSet B are candidates for being the answer.
• Iterate from i=2 \dots n and in each iteration trim the HashSet B by removing the elements which are no more the contenders to be the answer. And we can check if an element x of the HashSet is not a contender anymore by checking if none of A_i,A_i+1,A_i-1 are divisible by x (Then we can simply delete x from B as it can’t be the gcd obviously).
• Once we’ve iterated the entire array A our answer would just be the maximum element of B.
CODE FOR REFERENCE
#include<bits/stdc++.h>
using namespace std ;
vector <int> factors(int n) {
vector <int> s ;
for (int i=1;i*i<=n; i++) {
if (n%i == 0) {
if (n/i == i)
s.push_back(i) ;
else {
s.push_back(i) ;
s.push_back(n/i) ;
}
}
}
return s ;
}
void solve(){
int n;
cin>>n ;
vector<int>A(n) ;
for(int &x:A)
cin>>x ;
unordered_set<int>B ;
for(int i:{-1,0,1})
for(int x:factors(A+i))
B.insert(x) ;
for(int i=1;i<n;i++){
unordered_set<int>B1;
for(int x:B){
if(A[i]%x!=0&&(A[i]+1)%x!=0&&(A[i]-1)%x!=0)
continue  ;
else
B1.insert(x) ;
}
B=B1;
}
cout<<(*max_element(B.begin(),B.end())) <<'\n' ;
}
int main(){
int TC ;
cin>>TC ;
while(TC--)
solve() ;
}


PS: This is \displaystyle O(N \displaystyle \sqrt A_{max} ) and will TLE for a max-test with 10^5 elements each having value equal to 10^9. It’d be great if anyone can share a more efficient and correct approach.

2 Likes

Thank you