Solution

Method 1 – Euclidean Algorithm

Intuition

The greatest common divisor (GCD) of two numbers is the largest number that divides both. For an array, since the problem asks for the GCD of the smallest and largest number, we only need to find the min and max, then compute their GCD using the classic Euclidean algorithm.

Approach

Find the minimum value mn and maximum value mx in the array.
Use the Euclidean algorithm to compute the GCD of mn and mx.
Return the result.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int findGCD(vector<int>& nums) {\n        int mn = *min_element(nums.begin(), nums.end());\n        int mx = *max_element(nums.begin(), nums.end());\n        while (mx) {\n            int t = mn % mx;\n            mn = mx;\n            mx = t;\n        }\n        return mn;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> findGCD</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E

Related Tags