PROBLEM LINK:
Author: Harsh Dwivedi
Tester: Abhinav Prakash
DIFFICULTY:
SIMPLE
PREREQUISITES:
Data-Structures, Math.
PROBLEM:
We are given the divisors of a number x ( divisors except 1 and x itself ) , you have to print the number if only it is possible.
QUICK EXPLANATION:
Divisors of 6 are ( 1,2,3,6) Therefore, Divisors except 1 and the number 6 itself are ( 2 , 3). Thus, ans = 6.
SOLUTIONS:
Setter's Solution
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static FastScanner sc = new FastScanner();
public static void main(String[] args) {
int t = 0;
if (sc.hasNext())
t = sc.nextInt();
for (int i = 1; i <= t; i++) {
solve();
}
}
public static void solve() {
int n = sc.nextInt();
long[] a = sc.readArrayLong(n);
Arrays.sort(a);
long ans = a[0] * a[n - 1];
long[] b = new long[100001];
Vector<Long> x = new Vector<>();
for (int i = 0; i < n; i++)
x.add(a[i]);
Collections.sort(x);
Vector<Long> y = new Vector<>();
for (int i = 2; (long) i * i <= ans; i++) {
if (ans % i == 0) {
y.add((long) i);
if ((long) (i * i) != ans) {
y.add(ans / i);
}
}
}
Collections.sort(y);
for (int i = 0; i < n; i++) {
if (!x.get(i).equals(y.get(i))) {
System.out.println(-1);
return;
}
}
System.out.println(ans);
}
private static long gcd(long a, long b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
static void sort(int[] a) {
ArrayList<Integer> l = new ArrayList<>();
for (int i : a) l.add(i);
Collections.sort(l);
for (int i = 0; i < a.length; i++) a[i] = l.get(i);
}
static class FastScanner {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer("");
boolean hasNext() {
if (st != null && st.hasMoreTokens()) {
return true;
}
String tmp;
try {
br.mark(1000);
tmp = br.readLine();
if (tmp == null) {
return false;
}
br.reset();
} catch (IOException e) {
return false;
}
return true;
}
String next() {
while (!st.hasMoreTokens())
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
int[] readArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = nextInt();
return a;
}
long[] readArrayLong(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = nextLong();
return a;
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
}
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
int __gcd(int a, int b)
{
if( b == 0 ) return a ;
a %=b ;
return __gcd(b, a) ;
}
vector<long long> get_divisors(long long num)
{
set<long long> val ;
for(long long i = 2; i*i <= num; i++)
if( !(num%i) )
{
val.insert(i) ;
val.insert(num/i) ;
}
vector<long long> ans(val.begin(), val.end()) ;
return ans ;
}
int main( int argc, char **argv )
{
int t, n ;
cin >> t ;
while( t-- )
{
cin >> n ;
vector<long long> divs(n, 0) ;
for(int i = 0; i < n; i++)
cin >> divs[i] ;
set<long long> divset(divs.begin(), divs.end()) ;
sort( divs.begin(), divs.end() ) ;
long long num = divs[n-1] * divs[0] ;
vector<long long> vals = get_divisors(num) ;
bool done = true ;
for(int i = 0; i < vals.size(); i++)
if( !divset.count(vals[i]) )
{
done = false ;
break ;
}
if( done ) cout << num << endl ;
else cout << -1 << endl ;
}
return 0;
}