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[0];
int y = A[0] + 1;
int z = A[0] - 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?
@ssrivastava990 @ssjgz please help.