Find Greatest Common Divisor of Array
Problem
Given an integer array nums, return the greatest common divisor of the smallest number and largest number in nums.
nums = [2, 5, 6, 9, 10]2def find_gcd(nums):
a, b = min(nums), max(nums)
while b:
a, b = b, a % b
return afunction findGCD(nums) {
let a = Math.min(...nums), b = Math.max(...nums);
while (b) {
[a, b] = [b, a % b];
}
return a;
}class Solution {
public int findGCD(int[] nums) {
int a = Integer.MAX_VALUE, b = Integer.MIN_VALUE;
for (int x : nums) { a = Math.min(a, x); b = Math.max(b, x); }
while (b != 0) { int t = a % b; a = b; b = t; }
return a;
}
}int findGCD(vector<int>& nums) {
int a = *min_element(nums.begin(), nums.end());
int b = *max_element(nums.begin(), nums.end());
while (b) { int t = a % b; a = b; b = t; }
return a;
}Explanation
The problem only asks for the GCD of the smallest and largest numbers, so we ignore everything in between. We find min and max, then compute their greatest common divisor.
To get the GCD we use Euclid's algorithm. The idea: gcd(a, b) equals gcd(b, a % b). Repeatedly replacing the pair with (b, a % b) shrinks the numbers until the remainder becomes 0; the last nonzero value is the answer.
The compact line a, b = b, a % b does exactly this swap-and-reduce in one step. The loop runs while b is nonzero, and once b hits 0 we return a.
Example: nums = [2, 5, 6, 9, 10]. min is 2, max is 10. Start a=2, b=10. 2 % 10 = 2 so it becomes (10, 2); then 10 % 2 = 0 so it becomes (2, 0). b is 0, so the GCD is 2.
Finding min and max is one scan, and Euclid's loop is logarithmic, so this is very fast.