Max GCD Pair

Posted: 7 Nov, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given an array of positive integers. Find the GCD(Greatest Common Divisor) of a pair of elements such that it is maximum among all possible pairs. GCD(a, b) is the maximum number x such that both a and b are divisible by x.

For example: 
If the given array is {1, 5, 2, 3, 4}, the output will be 2 (which is GCD of 2 and 4, all other pairs have a GCD of 1)
Input format :
The first line of input contains a single integer 'T', representing the number of test cases or queries to be run. 
Then the 'T' test cases follow.

The first line of each test case contains a positive integer 'N', which represents the size of the array.

The next line contains 'N' single space-separated positive integers representing the elements of the array.
Output Format :
For each test case, print a single line containing a single integer denoting the maximum GCD value.

The output of each test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
2 <= N <= 10 ^ 4
1 <= ARR[i] <= 10 ^ 5

Where 'T' is the number of test cases, 'N' is the size of the array and ARR[i] is the ith element in the array.

Time Limit: 1 sec.
Approach 1

If a number is a divisor of two or more elements then it can be the GCD of the pair formed using those elements.

 

In this method, we will iterate over all the elements in the array and find the divisors of every element. We will also maintain a count array where the index represents the divisor and the value at that index is the number of elements in the given array having this as a divisor.

 

After the whole traversal, we can simply traverse the divisors from the maximum divisor to 1, and the first divisor that has counted more than 1 will be the maximum GCD value.

Try Problem