Description
Solutions
Find Maximum Possible GCD 🥭

You are given an integer R, and an array A consisting of positive integers. You can do this operation at most once (possibly zero times):

  • Choose any element of the array. Replace it with any integer X, such that 1 ≤ X ≤ R.

Find the maximum possible GCD of the entire array.

Constraints:

Example 1: 

Input:  R = 10, A = [2, 3, 4]
Output: 2 
Explanation:

We can change the second element from 3 to 2. Then GCD of the array becomes gcd(2,2,4)=2, which is the maximum possible.
Constraints:
  • 2 ≤ N ≤ 10^5 (N is length of array)
  • 1 ≤ R ≤ 10^5
  • 1 ≤ Ai ≤ 10^5
Thumbnail 0
Testcase
Result
Case 1

input:

output: