#1979
Find Greatest Common Divisor of Array
Easy Euclid's GCD
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the GCD of the smallest and largest numbers in the array.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: GCD of the smallest and largest number in the array.
Why this works: Euclid's rule gcd(a, b) = gcd(b, a % b) shrinks the numbers fast.
Example: nums = [2, 5, 6, 9, 10] → min 2, max 10
gcd(10, 2) → gcd(2, 0) → 2✦Hints open one at a time
Find min and max in one pass.
Euclid: gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a.
↗Approach
One pass for min and max, then Euclid's algorithm, which shrinks the numbers fast — O(log min(a, b)) steps.
</>Solution (Java)
class Solution {
public int findGCD(int[] nums) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int x : nums) {
min = Math.min(min, x);
max = Math.max(max, x);
}
return gcd(max, min);
}
private int gcd(int a, int b) {
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return a;
}
}!Common mistake
Computing the GCD of all elements — the problem asks only for min and max.
Complexity
- Time: O(n + log M).
- Space: O(1).
