Find Maximum Possible GCD 🥭
Barclays● MediumOAProblem statement
You are given an integer R and an array A of positive integers. You may perform the following operation at most once: choose one array element and replace it with any integer X satisfying 1 <= X <= R.
Return the maximum possible greatest common divisor of all elements in A. You may also leave the array unchanged.
Function
findMaximumPossibleGCD(R: int, A: int[]) → intExamples
Example 1
R = 10A = [2, 3, 4]return = 2Replace the second element, 3, with 2. The array becomes [2, 2, 4], whose greatest common divisor is 2. No allowed replacement can produce a larger common divisor.
Constraints
2 <= A.length <= 1000001 <= R <= 1000001 <= A[i] <= 100000