GCD of an Array

Medium · rating 1250 · math, number-theory

The first line contains n. The second line contains n positive integers. Print the greatest common divisor of all of them.

Constraints: 1 ≤ n ≤ 10⁵

Editorial

GCD of an Array extends the pairwise greatest common divisor to a whole list — a number-theory problem built on the Euclidean algorithm.

Approach

The GCD is associative: gcd(a, b, c) = gcd(gcd(a, b), c). Fold the array carrying a running GCD — it only ever shrinks, and reaching 1 lets you stop early.

from math import gcd
g = 0
for x in nums:
    g = gcd(g, x)
    if g == 1: break
return g

Complexity

Time: O(n log(max value)). Space: O(1).

Open GCD of an Array in Code Arena →