Difficulty
Easy-medium
Problem
Solution
For some k to divide gcd(arr_i,arr_j), it must divide both arr_i and arr_j, that means there must be atleast two elements in the array which are divisible by k. So for all the numbers from 2 to 2\cdot 10^6 we will find out how many elements are there in the array which are divisible by it. The smallest number which divides atmost 1 element of the array is our answer.
Time Complexity
O(NlogN)
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n;
cin>>n;
const int N=2e6;
vector<int>count(N+1); //count[i] stores the number of time i appears in the array
for(int i=0; i<n; i++){
int a;
cin>>a;
count[a]++;
}
vector<int>cnt(N+1); //cnt[i] stores the number of elements in the array that are divisible by i
for(int j=2; j<=N; j++){
for(int k=1; j*k<=N; k++){
cnt[j]+=count[j*k];
}
}
int ans=N+1;
for(int j=2; j<=N; j++){
if(cnt[j]<2){
ans=j;
break;
}
}
cout<<ans;
return 0;
}