Max GCD Pair

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
16 upvotes
Asked in companies
AmazonVisaApple

Problem statement

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)
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
3
5
5 2 4 3 1
5
2 4 6 5 6
10
4 2 10 8 6 4 3 2 1 7
Sample Output 1:
2
6
4
Explanation for Sample Input 1:
In the 1st test case, pair (2,4) has a maximum GCD value of 2, all other pairs have a GCD of 1.

In the 2nd test case, pair (6,6) has a maximum GCD value of 6, all other pairs have GCD less than 6.

In the 3rd test case, pair (4,8) has a maximum GCD value of 4, all other pairs have GCD less than 4.
Sample Input 2:
2
4
2 4 6 8 
5
1 2 3 4 5
Sample Output 2:
4
2
Hint

What if a number is a divisor of two or more elements of the given array?

Approaches (2)
Brute force

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.

Time Complexity

O(N * sqrt(M) + M ), Where ‘M’ denotes the largest number in the array, N is the size of the given array.
 

It takes O(N) time to traverse the array and for each element in the array, we can calculate divisors of a number by iterating from 2 to square root of the number because all the divisors are present in pairs. So, it takes O(sqrt(M)) time to calculate the divisors of the element.

Also, it takes O(M) time to traverse the divisor count array. Thus, the final time complexity is O(N * sqrt(M) + M ).

Space Complexity

O(M), Where ‘M’ denotes the largest number in the array.
 

O(M) extra space is needed to make a divisor count array.

Code Solution
(100% EXP penalty)
Max GCD Pair
Full screen
Console