Maximum GCD

Hard
0/120
Average time to solve is 40m
profile
Contributed by
1 upvote
Asked in company
Capegemini Consulting India Private Limited

Problem statement

You are given an array 'A' of length 'N'. You can perform the following operation at most once.

Choose any element of the array and replace it with 'X', 1 <= 'X' <= 'M'.

Return the maximum possible GCD of the array after performing the operation.

For Example:- 
Let 'N' = 3, 'M' = 5, and 'A' = [4, 3, 2].
We can replace 3 with 2.
The maximum possible GCD is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:- 
First-line contains an integer 'T', which denotes the number of test cases.
For every test case:-
First-line contains two integers, 'N', and 'M'.
Second-line contains 'N' space-separated integers, elements of array 'A'.
Output Format:- 
For each test case, Return the maximum possible GCD of the array after performing the operation.
Note:- 
You don’t need to print anything. Just implement the given function.
Constraints:- 
1 <= 'T' <= 10
1 <= 'N' , 'M' <= 10^5
1 <= 'A[i]' <= 10^5

The Sum of 'N' overall test cases does not exceed 10^5.
Time Limit: 1 sec
Sample Input 1:-
2
4 5
2 5 6 12
2 4 
10 15
Sample Output 1:-
2
5
Explanation of sample input 1:-
First test case:-
We can replace 5 with 4.
The maximum possible GCD is 2.

Second test case:-
We do not need to replace any element.
The maximum possible GCD is 5.
Sample Input 2:-
2
5 13
3 4 2 8 7
3 12
4 14 13
Sample Output 2:-
1
2
Hint

Does the frequency of the factors of the elements matter?

Approaches (1)
Array, Maths, Hashing.

Approach:-

 

  • First, we traverse in 'A', and for each element:
    • We increase the frequency of the factor of the current element.
    • Iterate using 'j' from 1 to square root('A[i]'):
      • If 'j' is a factor of A[i]:
        • freq[j]++.
        • if('j' != 'A[i]'/'j'):
          • freq[A[i]/j]++.
  • Then from 1 to 1e5:
    • If the element has a frequency greater than 'N' - 1:
      • This means we can change at most one element and can get this as our gcd.
      • Then, we find all the factors of this element.
      • If the factor is less than or equal to 'M':
        • Then we update the answer with this factor.
  • Return the answer after checking for all elements from 1 to 1e5.

 

Algorithm:-
 

  • Initialize an integer array 'freq'.
  • Initialize an integer variable 'ans'.
  • Iterate from 1 to 'N:
    • 'ans' = __gcd('ans', A[i]).
    • Iterate using 'j' from 1 to square root('A[i]'):
      • If 'j' is a factor of A[i]:
        • 'freq[j]++'.
        • if('j' != 'A[i]'/'j'):
          • freq[A[i]/j]++.
  • Iterate using 'i' from 1 to 1e5:
    • If ('freq[i]' >= 'N' - 1):
      • Iterate using 'j' from 1 to square root(i):
        • If 'j' is a factor of 'i' and 'j' <= 'M':
          • 'ans' = max('ans', 'j').
          • if('i'/'j' <= 'M'):
            • 'ans' = max('ans', 'i'/'j').
  • Return 'ans' which is the required answer.
Time Complexity

O(N*sqrt(MAXA)), where 'N' is the length of the array 'A' and ‘MAXA’ is the largest element in the array.
 

We are traversing from 1 to 'N' and finding factors, and the complexity associated with this is O(N*sqrt(MAXA)). Hence, the overall time complexity is of the order O(N*sqrt(MAXA)).

Space Complexity

O(N), where 'N' is the length of the array 'A'.

 

We are creating 'freq' to store frequency, So the Space Complexity is O(N).

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