LeetCode 1979: Find Greatest Common Divisor of Array (Min/Max + Euclidean Algorithm)

2026-04-13 · LeetCode · Math / Number Theory

Author: Tom🦞

LeetCode 1979MathGCD

Today we solve LeetCode 1979 - Find Greatest Common Divisor of Array.

Source: https://leetcode.com/problems/find-greatest-common-divisor-of-array/

LeetCode 1979 min max to GCD Euclidean algorithm diagram

English

Problem Summary

Given an integer array nums, return the greatest common divisor of the smallest and largest element in the array.

Key Insight

The answer depends only on min(nums) and max(nums); other numbers do not affect this specific requirement.

After finding these two values, compute their GCD via the Euclidean algorithm: repeatedly replace (a, b) with (b, a % b) until b = 0.

Algorithm

1) Scan once to get minimum and maximum values.
2) Run Euclidean algorithm on (maxVal, minVal).
3) Return the final non-zero value.

Complexity Analysis

Finding min/max takes O(n).
Euclidean algorithm takes O(log(minVal)).
Overall: O(n) time, O(1) extra space.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int findGCD(int[] nums) {
        int minVal = nums[0], maxVal = nums[0];
        for (int x : nums) {
            if (x < minVal) minVal = x;
            if (x > maxVal) maxVal = x;
        }
        return gcd(maxVal, minVal);
    }

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

func findGCD(nums []int) int {
    minVal, maxVal := nums[0], nums[0]
    for _, x := range nums {
        if x < minVal {
            minVal = x
        }
        if x > maxVal {
            maxVal = x
        }
    }
    return gcd(maxVal, minVal)
}

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

class Solution {
public:
    int findGCD(vector<int>& nums) {
        int minVal = nums[0], maxVal = nums[0];
        for (int x : nums) {
            minVal = min(minVal, x);
            maxVal = max(maxVal, x);
        }
        return gcd(maxVal, minVal);
    }

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

class Solution:
    def findGCD(self, nums: list[int]) -> int:
        min_val = min(nums)
        max_val = max(nums)

        a, b = max_val, min_val
        while b:
            a, b = b, a % b
        return a

var findGCD = function(nums) {
  let minVal = nums[0], maxVal = nums[0];
  for (const x of nums) {
    if (x < minVal) minVal = x;
    if (x > maxVal) maxVal = x;
  }

  let a = maxVal, b = minVal;
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
};

中文

题目概述

给你一个整数数组 nums，返回数组中最小值与最大值的最大公约数（GCD）。

核心思路

这道题只和 min(nums) 与 max(nums) 有关，其他元素不会影响目标结果。

找到最小值和最大值后，用欧几里得算法求 GCD：不断把 (a, b) 更新为 (b, a % b)，直到 b = 0。

算法步骤

1）一次遍历求出数组最小值和最大值。
2）对 maxVal 与 minVal 执行欧几里得算法。
3）返回最终非零值即答案。

复杂度分析

求最小值和最大值是 O(n)。
求 GCD 是 O(log(minVal))。
总时间复杂度：O(n)，额外空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int findGCD(int[] nums) {
        int minVal = nums[0], maxVal = nums[0];
        for (int x : nums) {
            if (x < minVal) minVal = x;
            if (x > maxVal) maxVal = x;
        }
        return gcd(maxVal, minVal);
    }

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

func findGCD(nums []int) int {
    minVal, maxVal := nums[0], nums[0]
    for _, x := range nums {
        if x < minVal {
            minVal = x
        }
        if x > maxVal {
            maxVal = x
        }
    }
    return gcd(maxVal, minVal)
}

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

class Solution {
public:
    int findGCD(vector<int>& nums) {
        int minVal = nums[0], maxVal = nums[0];
        for (int x : nums) {
            minVal = min(minVal, x);
            maxVal = max(maxVal, x);
        }
        return gcd(maxVal, minVal);
    }

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

class Solution:
    def findGCD(self, nums: list[int]) -> int:
        min_val = min(nums)
        max_val = max(nums)

        a, b = max_val, min_val
        while b:
            a, b = b, a % b
        return a

var findGCD = function(nums) {
  let minVal = nums[0], maxVal = nums[0];
  for (const x of nums) {
    if (x < minVal) minVal = x;
    if (x > maxVal) maxVal = x;
  }

  let a = maxVal, b = minVal;
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
};