Funcia
Lv.1arraygcdmathprefix-sum

Max GCD After Removing One

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Remove exactly one element from the positive integer array nums so that the greatest common divisor of the remaining elements is as large as possible, and return that GCD. If one element remains, its GCD is the element itself.

Examples

numsresult
[12, 15, 18]6
[8, 7, 16, 24]8
[5, 9]9

Example 1 — removing 15 leaves gcd⁡(12,18)=6\gcd(12, 18) = 6, the best choice.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(nums: int[]) → int

Constraints

  • 2≤2 \le nums.length ≤200,000\le 200{,}000
  • 1≤1 \le nums[i] ≤109\le 10^9

Expected complexity

Time
O(N log V)
Space
O(N)

Examples

numsExpected
[12,15,18]6
[8,7,16,24]8
[5,9]9

Hint

Hint

Removing nums[i] leaves gcd(prefix GCD of nums[0..i-1], suffix GCD of nums[i+1..]). Build both arrays in one pass each, using gcd⁡(0,x)=x\gcd(0, x) = x for the empty side. Recomputing the GCD of everything else for each index is O(N2log⁡V)O(N^2 \log V) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251018 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.