Lv.1arraygcdmathprefix-sum
Max GCD After Removing One
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 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
| nums | result |
|---|---|
[12, 15, 18] | 6 |
[8, 7, 16, 24] | 8 |
[5, 9] | 9 |
Example 1 — removing 15 leaves , 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
-
nums.length -
nums[i]
Expected complexity
- Time
- O(N log V)
- Space
- O(N)
Examples
| nums | Expected |
|---|---|
[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 for the empty side. Recomputing the GCD of everything else for each index is and exceeds
the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1018 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 11 | verdict only |
| performance | 60 | 4 | verdict only |