Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

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 )
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
Full screen
Console