// 演算法 / 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;
}