1979. Find Greatest Common Divisor of Array

題目 / Problem

中文： 給定一個整數陣列 nums，請找出陣列中最小值與最大值的最大公因數（GCD），並回傳這個結果。最大公因數是指能同時整除兩個數字的最大正整數。

English: Given an integer array nums, return the greatest common divisor (GCD) of the smallest and largest numbers in nums. The GCD of two numbers is the largest positive integer that divides both of them evenly (with no remainder).

Constraints / 限制： - 2 <= nums.length <= 1000（陣列至少有 2 個元素 / array has at least 2 elements） - 1 <= nums[i] <= 1000（每個元素都是 1 到 1000 的正整數 / each element is a positive integer from 1 to 1000）

Worked example / 範例： nums = [2,5,6,9,10] → 最小值是 2，最大值是 10，gcd(2, 10) = 2，所以答案是 2。

名詞解釋 / Glossary

• 最大公因數 / Greatest Common Divisor (GCD)： 能同時整除兩個數的最大正整數。例如 gcd(12, 18) = 6，因為 6 是同時整除 12 和 18 的最大數。/ The largest positive integer that divides both numbers exactly.
• 整除 / Divides evenly： 一個數除以另一個數後餘數為 0。例如 10 ÷ 2 = 5 餘 0，所以 2 整除 10。/ One number divides another when the remainder is zero.
• 取餘數運算 % / Modulo operator： a % b 得到 a 除以 b 之後的餘數。若 a % b == 0 表示 b 能整除 a。/ a % b gives the remainder of a divided by b; a zero remainder means b divides a.
• 歐幾里得演算法 / Euclidean algorithm： 一種快速求 GCD 的方法，反覆用「較大數對較小數取餘數」直到餘數為 0。這是本題的核心技巧。/ A fast method to compute GCD by repeatedly replacing the larger number with the remainder until it becomes zero.
• 陣列走訪 / Array traversal： 用迴圈把陣列的每個元素看過一遍，這裡用來找最小值與最大值。/ Looping over every element once, here used to find the min and max.

思路

中文：最直覺的暴力法是先掃一遍陣列找到最小值 mn 和最大值 mx，然後從 1 到 mn 逐一嘗試每個數 d，只要 mn % d == 0 且 mx % d == 0，就記下 d；掃到最後留下的最大 d 就是答案。這個方法完全正確，因為它真的把所有可能的公因數都檢查了一遍，時間是 O(n + mn)，在本題 mn ≤ 1000 的限制下也夠快。但它有點浪費：我們其實不需要試那麼多數。更聰明的做法是用歐幾里得演算法求 GCD。它的核心觀察是：gcd(a, b) = gcd(b, a % b)。為什麼成立？因為任何同時整除 a 和 b 的數，也一定整除 a % b（餘數），反之亦然，所以兩組公因數完全一樣，最大的那個自然也一樣。我們不斷用這個式子把數字變小，當其中一個變成 0 時，另一個就是答案（因為任何數和 0 的 GCD 就是那個數本身）。所以整體流程是：走訪一次陣列找出 mn 與 mx，再對這兩個數跑歐幾里得演算法。

English: The brute-force idea is to first scan the array once to find the minimum mn and maximum mx, then try every candidate divisor d from 1 up to mn, keeping the largest d for which both mn % d == 0 and mx % d == 0. That is fully correct and, since mn ≤ 1000 here, fast enough — but it tests far more numbers than necessary. The cleaner approach is the Euclidean algorithm, built on the identity gcd(a, b) = gcd(b, a % b). It works because any number that divides both a and b must also divide their remainder a % b, and vice versa — so the two pairs share exactly the same set of common divisors, hence the same greatest one. We keep shrinking the pair with this rule until one value hits 0; the other value is then the answer, since gcd(x, 0) = x. So the whole plan is: one pass to find mn and mx, then run Euclid on just those two numbers.

逐步走查 / Walkthrough

Input / 輸入：nums = [2,5,6,9,10]

Step 1 — 找最小值與最大值 / Find min and max (one pass):

結果 / Result: mn = 2, mx = 10.

Step 2 — 歐幾里得演算法求 gcd(2, 10) / Euclidean algorithm on gcd(2, 10):

我們設 a = mx = 10, b = mn = 2，反覆執行 (a, b) → (b, a % b)：

當 b == 0 時停止，答案就是 a = 2。/ When b reaches 0, the answer is a = 2. ✅ 符合預期輸出 2。

Solution — C

// 演算法 / Algorithm:
// 1) 走訪陣列一次，找出最小值 mn 與最大值 mx。
//    Scan the array once to find the min (mn) and max (mx).
// 2) 用歐幾里得演算法計算 gcd(mn, mx) 並回傳。
//    Use the Euclidean algorithm to compute gcd(mn, mx) and return it.

int findGCD(int* nums, int numsSize) {
    // mn 先設為第一個元素，之後只會變小或不變 / start mn at first element, it only shrinks
    int mn = nums[0];
    // mx 先設為第一個元素，之後只會變大或不變 / start mx at first element, it only grows
    int mx = nums[0];

    // 從第 1 個索引開始逐一比較每個元素 / loop over each element to update mn and mx
    for (int i = 1; i < numsSize; i++) {
        // 若當前元素比 mn 小，更新最小值 / if smaller than mn, it becomes the new min
        if (nums[i] < mn) mn = nums[i];
        // 若當前元素比 mx 大，更新最大值 / if larger than mx, it becomes the new max
        if (nums[i] > mx) mx = nums[i];
    }

    // 歐幾里得演算法：a、b 為要求 GCD 的兩個數 / Euclid: a and b are the two numbers
    int a = mx;  // 用較大的當 a（順序其實不影響結果）/ larger as a (order doesn't affect result)
    int b = mn;  // 較小的當 b / smaller as b

    // 當 b 還不是 0 就繼續縮小 / keep looping until b becomes 0
    while (b != 0) {
        int r = a % b;  // r 是 a 除以 b 的餘數 / r is the remainder of a divided by b
        a = b;          // 把 b 搬到 a / shift b into a
        b = r;          // 把餘數搬到 b / shift remainder into b
    }

    // 迴圈結束時 b 為 0，a 就是最大公因數 / when b is 0, a holds the GCD
    return a;
}

Solution — C++

// 演算法 / Algorithm:
// 1) 用一次走訪找出陣列的最小值與最大值。
//    Find the array's min and max in a single pass.
// 2) 對這兩個數執行歐幾里得演算法求 GCD 並回傳。
//    Run the Euclidean algorithm on those two numbers and return the GCD.

#include <vector>     // 提供 std::vector 容器 / provides std::vector
#include <algorithm>  // 提供 min_element / max_element / provides min_element / max_element

class Solution {
public:
    int findGCD(std::vector<int>& nums) {
        // *min_element(...) 回傳範圍內最小值；* 是解參考取出該值
        // *min_element(...) returns the smallest value in the range; * dereferences the iterator
        int mn = *std::min_element(nums.begin(), nums.end());
        // 同理取得最大值 / likewise get the largest value
        int mx = *std::max_element(nums.begin(), nums.end());

        // 歐幾里得演算法，用 while 迴圈反覆取餘數 / Euclidean algorithm via repeated remainder
        int a = mx, b = mn;   // a、b 為兩個待求 GCD 的數 / the two numbers whose GCD we want
        while (b != 0) {      // b 變成 0 時停止 / stop once b reaches 0
            int r = a % b;    // 餘數 / remainder of a divided by b
            a = b;            // b 成為新的 a / b becomes the new a
            b = r;            // 餘數成為新的 b / remainder becomes the new b
        }
        return a;             // a 即為最大公因數 / a is the GCD

        // 小提醒：C++17 起也可直接用 std::gcd(mn, mx)（需 #include <numeric>）
        // Note: since C++17 you could also write std::gcd(mn, mx) with <numeric>.
    }
};

複雜度 / Complexity

• Time: O(n + log(min(mn, mx))) — 找最小/最大值需要走訪整個陣列一次，這是 O(n)，n 是陣列長度。歐幾里得演算法每一步至少讓數字減半左右，所以只需約 log 次迭代，非常快。整體由走訪陣列主導。/ The single pass to find min/max is O(n) where n is the array length; the Euclidean loop runs about log-many steps because the numbers shrink rapidly. The scan dominates.
• Space: O(1) — 只用了 mn、mx、a、b、r 等固定數量的變數，沒有隨輸入大小成長的額外空間。/ Only a fixed number of scalar variables are used; no extra memory grows with the input size.

Pitfalls & Edge Cases

• 相等的最小值與最大值 / Equal min and max（例如 [3,3]）： 當 mn == mx 時，gcd(x, x) = x，歐幾里得演算法第一步 x % x = 0 直接得到答案 x，程式自然正確處理。/ When all-equal, gcd(x, x) = x; Euclid handles it since x % x = 0 immediately.
• 不要對 0 取餘數 / Never take remainder by 0： 迴圈條件是 while (b != 0)，保證 a % b 永遠不會除以 0。若寫錯條件可能導致除零錯誤（程式崩潰）。/ The b != 0 guard ensures a % b never divides by zero, which would crash.
• 初始化 min/max 的常見錯誤 / Common min/max init bug： 在 C 版本把 mn、mx 都初始化為 nums[0]（陣列真實存在的值），而不是 0 或某個猜測值；用 0 當初始最小值會讓 mn 永遠是 0（因為沒有元素比 0 小），結果全錯。/ Initialize from nums[0], not 0 — seeding mn = 0 would wrongly keep min at 0.
• 不會溢位 / No overflow risk： 因為 nums[i] ≤ 1000，所有中間值都很小，int 綽綽有餘，不需要 long long。/ Values are ≤ 1000, so int is safe; no need for wider types.
• GCD 參數順序 / Argument order doesn't matter： 即使一開始 a < b，第一輪 a % b = a、交換後就自動把大的放前面，結果不變。/ Even if a < b initially, the first iteration swaps them automatically; the result is the same.