Header Ads Widget

Little Elephant and Divisors | codechef solution

Rajnish Tripathi 10:27

Problem

The Little Elephant from the Zoo of Lviv has an array A that consists of N positive integers. Let A[i] be the i-th number in this array (i = 1, 2, ..., N).

Find the minimal number x > 1 such that x is a divisor of all integers from array A. More formally, this x should satisfy the following relations:

A[1] mod x = 0, A[2] mod x = 0, ..., A[N] mod x = 0,

where mod stands for the modulo operation. For example, 8 mod 3 = 2, 2 mod 2 = 0, 100 mod 5 = 0 and so on. If such number does not exist, output -1.

Input

The first line of the input contains a single integer T, the number of test cases. T test cases follow. The first line of each test case contains a single integer N, the size of the array A for the corresponding test case. The second line contains N space separated integers A[1], A[2], ..., A[N].

Output

For each test case output a single line containing the answer for the corresponding test case.

Constraints

1 ≤ T ≤ 100000
1 ≤ N ≤ 100000
The sum of values of N in each test file does not exceed 100000
1 ≤ A[i] ≤ 100000

Sample 1:

Input
Output
2
3
2 4 8
3
4 7 5
2
-1

Explanation:

Case 1. Clearly 2 is a divisor of each of the numbers 2, 4 and 8. Since 2 is the least number greater than 1 then it is the answer.

Case 2. Let's perform check for several first values of x.

x4 mod x7 mod x5 mod x
2011
3112
4031
5420
6415
7405
8475
9475

As we see each number up to 9 does not divide all of the numbers in the array. Clearly all larger numbers also will fail to do this. So there is no such number x > 1 and the answer is -1.

 Code(C++):-

#include <bits/stdc++.h>
using namespace std;

//defining macros
#define fast_in_out \
ios_base::sync_with_stdio(false);\
cin.tie(NULL);
#define ll long long int
int main() {
fast_in_out;
    ll t; cin>>t;
    while(t--){
     ll n; cin>>n;
     ll a[n], gcd=0;
     for(ll i=0; i<n; i++){ cin>>a[i]; gcd= __gcd(gcd, a[i]); }
    
     if(gcd==1){ cout<<-1<<endl; }
     else{
     ll res=gcd;
     for(ll i=2; i<=sqrt(gcd); i++){
     if(gcd%i==0){
     res= min(res, i);
     res= min(res, gcd/i);
     }
     }
     cout<<res<<endl;
     }
    }
    return 0;
}

Code(JAVA):-
import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
public static int gcd(int a,int b)
{
if(a==0)
return b;
if(b==0)
return a;
b%=a;
return(gcd(b,a));
}
    public static void main (String[] args) throws java.lang.Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine()),n,m;
        while(t-->0)
        {
         n=Integer.parseInt(br.readLine());
         String s[]=br.readLine().split(" ");
         m=Integer.parseInt(s[0]);
         for(int i=0;i<n;i++)
         m=gcd(m,Integer.parseInt(s[i]));
         n=((int)Math.sqrt(m))+1;
         if(m<2)
         m=-1;
         else
         for(int i=2;i<n;i++)
         if(m%i==0)
         {
         m=i;
         break;
         }
         System.out.println(m);
        }
    }
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Tags:

Post a Comment

0 Comments