How To Solve Maximum GCD , ( CP Potpourri Prelims )

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.

1 Like

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

1 Like

Okay thanks

1 Like

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 :slightly_smiling_face:, 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?

@dhruv788 i also couldn’t understand this thing can someone clear this

@cubefreak777
Yes, you are correct thanks for pointing this error!!

1 Like

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

@admin , can you please make other’s submission visible for this contest.

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?