PROBLEM LINK:
Author: Mostafijur Riju
Tester 1: Harsh Raj
Tester 2: Chandan Boruah
Editorialist: Mostafijur Riju
DIFFICULTY:
SIMPLE-EASY.
PREREQUISITES:
Greedy,Math, array
PROBLEM:
Find the smallest prime number in the array that has exactly two unique multiples present in the array.
QUICK EXPLANATION:
To find the solution of above problem:
1. Maintain a sieve of primes(SIEVE OF ERATOSTHENES APPROACH).
2. Hash the entire array.
3. Traverse the entire array and check for a prime if corresponding to it exactly two unique multiples are present in the array.
4. Output the smallest prime.
5. If no prime is present or no prime has exactly two unique multiples output -1.
DETAILED EXPLANATION:
The problems asks for the smallest prime corresponding to which exactly two unique multiples are present. To check for a prime the most efficient method is to maintain a sieve. Hence maintaining a sieve and hashing the array will allow us to check whether a number is prime or not in O(1) time as with hashing we don’t need to check for duplicate elements again and again. Iterating over the hashmap at first we need to check whether an element is prime or not, if yes then we need to count the number of unique multiples present in the array it has. It can be done efficiently by just checking over the hashmap if a particular multiple is present or not by using the same sieve approach. Hence if a prime is found having exactly two unique primes we need to print the smallest prime else -1.
SOLUTIONS:
Solution of riju321
#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool prime[100005]={0};
void sieve(){
prime[0]=prime[1]=1;
for(ll i=2;i*i<=100000;i++){
if(prime[i]==0){
for(ll j=i*i;j<=100000;j+=i)
prime[j]=1;
}
}
}
int main(){
sieve();
ll n;
cin>>n;
ll max_element = INT_MIN;
map<ll,ll>mp;
ll e;
for(ll i=0;i<n;i++){
cin>>e;
mp[e]++;
max_element = max(max_element,e);
}
ll ans = -1;
for(auto it=mp.begin();it!=mp.end();it++){
ll c=0;
if(prime[it->first]==0){
for(ll i=it->first;i<=max_element;i+=it->first){
if(mp[i])
++c;
}
}
if(c==2){
ans=it->first;
break;
}
}
cout<<ans<<"\n";
return 0;
}
Solution of harshraj22
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+7;
vector<int> v(N,0),pr;
void sieve(){
for(int i=2;i<v.size();i++){
if(v[i]==0){
pr.push_back(i);
for(int j=i+i;j<v.size();j+=i)
v[j] = 1;
}
}
}
int main(){
int n; cin >> n;
sieve();
vector<int> a(N,0),mult(N,0);
set<int> input;
for(int i=0;i<n;i++){
int var; cin >> var;
a[var] += 1; input.insert(var);
}
int Max=*input.rbegin(),Min=*input.begin();
for(auto it:input){
for(int i=it;i<=Max;i+=it){
mult[it] += a[i];
}
mult[it] -= 1;
}
for(auto it:input){
// cout << it << " mult is " << mult[it] << '\n';
if(v[it] == 0 && mult[it]==2){
cout << it << '\n';
return 0;
}
}
cout << -1 << '\n';
return 0;
}
Solution of chandubaba
using System;
using System.Collections.Generic;
class some
{
public static void Main()
{
int n=int.Parse(Console.ReadLine());
int[]arr=new int[1000001];
string[]ss=Console.ReadLine().Split();
for(int i=0;i<n;i++)
{
arr[int.Parse(ss[i])]++;
}
int[]primes=new int[1000001];
for(int i=2;i*i<=primes.Length;i++)
{
if(primes[i]==0)
for(int j=i+i;j<primes.Length;j+=i)
{
primes[j]=1;
}
}
bool b=false;
for(int i=2;i*i<=arr.Length;i++)
{
int count=0;
if(arr[i]>=1 && primes[i]==0)
{
for(int j=i;j<arr.Length;j+=i)
{
if(arr[j]>=1)
count++;
}
if(count==2){b=true;Console.WriteLine(i);break;}
}
}
if(!b)Console.WriteLine(-1);
}
}