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:Solution: 42877615 | CodeChef

I used loop for m to 1 and got tle , thank you bhaiya for ur approach

Your solution is wrong. It got accepted because test-cases were weak.

## TEST_CASE

```
1
10
12 13 17 15 3 3 3 5 11 17
```

The answer for this test-case is 4 but your code gives 3

@vaibhav_717

hey can you tell me the complexity of your code if i couldnāt understand. what is the maximum no of elements we can have in the set ie factors of(a[i],a[i]-1,a[i]+1) where a[i] is smallest element which can be upto 1e9 in which case our set can have large size which may result in tle can you clear this?

That solution is wrong , It passed because the test cases are weak An example TC, Answer should be 4 but mine is giving 3.

1

3

12 5 3

I do not know why your code accepted but I think it is wrong to approach.Maybe I am wrong .

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?

Anyone?