1979. Find Greatest Common Divisor of Array

Array
Math
Number Theory

TIME

O(n + log V)

SPACE

O(1)

Intuition

The problem states exactly what to compute: only the minimum and maximum matter, so find them and take their GCD.

Approach

Scan nums once, tracking the minimum and maximum values.
Return gcd(min, max) via the Euclidean algorithm (gcd(a, b) = gcd(b, a % b) until b == 0).

Complexity

Time: O(n + log V), one pass plus the Euclidean algorithm
Space: O(1)

Edge Cases

All elements equal → min == max → the GCD is that value itself (Example 3)
Coprime min and max → 1 (Example 2)
Min divides max → the answer is the min
Array length is at least 2, so min and max always exist

Code

from typing import List
from math import gcd


class Solution:
    def findGCD(self, nums: List[int]) -> int:
        """
        1979. Find Greatest Common Divisor of Array
        Time: O(n + log V)
        Space: O(1)
        """
        return gcd(min(nums), max(nums))

/**
 * 1979. Find Greatest Common Divisor of Array
 * Time: O(n + log V)
 * Space: O(1)
 */
class Solution {
    public int findGCD(int[] nums) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int x : nums) {
            min = Math.min(min, x);
            max = Math.max(max, x);
        }
        return gcd(min, max);
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
}