Math Fundamentals18 sections · 814 units
Open in Course

GCD of Multiple Numbers

Extending the algorithm

To find gcd(a, b, c), compute gcd(gcd(a, b), c). The GCD operation is associative: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c).

For an array of n numbers, fold from left to right: result = a[0], then result = gcd(result, a[1]), then gcd(result, a[2]), and so on.

This takes O(n log max(a)) time. Same idea works for LCM of multiple numbers.