Last Updated: 8 Dec, 2022

Maximum GCD

Hard

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.

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

Solve now

Approaches

01 Approach

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.

Solve now