FastPrep
Problem · Array

Find Maximum Possible GCD 🥭

Learn this problem
● MediumBarclayOA

Problem statement

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:

Function

findMaximumPossibleGCD(R: int, A: int[]) → int

Examples

Example 1

R = 10A = [2, 3, 4]return = 2
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

    • More Barclay problems

    drafts saved locally
    public int findMaximumPossibleGCD(int R, int[] A) {
    // write your code here
}
    R10
    A[2, 3, 4]
    expected2
    checking account