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