Help needed in Maximum GCD (CP Potpourri)

general
, , , , ,
#1

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.

#2

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

#3

So any greedy fails right?

#4

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

#5

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

#6

may you please share the link to question?

#7

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[0]+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
#8

Thank you