Find Greatest Common Divisor of Array — Problem & Solution
Find Greatest Common Divisor of Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Find Greatest Common Divisor of Array is an easy coding problem on arrays, math and number theory, asked in Amazon, TCS, Infosys and Accenture interviews.
- Difficulty: Easy
- Topics: Arrays, Math, Number Theory
- Asked at: Amazon, TCS, Infosys, Accenture
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums, return the greatest common divisor of its smallest and largest elements.
The greatest common divisor of two numbers is the largest positive integer that divides both of them.
Example 1
Input: nums = [2,5,6,9,10]
Output: 2
Explanation: The smallest is 2 and the largest is 10; gcd(2, 10) = 2.
Example 2
Input: nums = [7,5,6,8,3]
Output: 1
Explanation: gcd(3, 8) = 1.
Example 3
Input: nums = [3,3]
Output: 3
Constraints
2 <= nums.length <= 401 <= nums[i] <= 1000
Hints for Find Greatest Common Divisor of Array
Hint 1
One pass finds both the minimum and the maximum.
Hint 2
Euclid's algorithm computes the gcd:
gcd(a, b) = gcd(b, a mod b), ending when b reaches 0.Hint 3
The smallest and largest may be the same element when every value is equal — that is fine, gcd(x, x) = x.
How to solve Find Greatest Common Divisor of Array
Find the minimum and maximum in one pass, then apply Euclid's algorithm to the pair.
Approach
- Compute
a = min(nums),b = max(nums). - While
b != 0, set(a, b) = (b, a % b). - Return
a.
Why it works
Any common divisor of a and b also divides a mod b, and vice versa, so the gcd is preserved by each step while the second argument strictly shrinks to zero. The last non-zero value is the gcd.
Complexity
- Time —
O(n + log(max)) - Space —
O(1)
Pitfalls
- When every element is equal, min and max coincide and
gcd(x, x) = x. - Only the extreme elements matter — the gcd of the whole array is a different question.
Reference solution
Python
def findGCD(nums):
a, b = min(nums), max(nums)
while b:
a, b = b, a % b
return aJava
public static int findGCD(int[] nums) {
int lo = nums[0], hi = nums[0];
for (int x : nums) {
if (x < lo) lo = x;
if (x > hi) hi = x;
}
while (lo != 0) {
int t = hi % lo;
hi = lo;
lo = t;
}
return hi;
}C++
int findGCD(vector<int>& nums) {
int lo = nums[0], hi = nums[0];
for (int x : nums) {
if (x < lo) lo = x;
if (x > hi) hi = x;
}
while (lo != 0) {
int t = hi % lo;
hi = lo;
lo = t;
}
return hi;
}JavaScript
var findGCD = function(nums) {
let lo = nums[0], hi = nums[0];
for (let i = 1; i < nums.length; i++) {
if (nums[i] < lo) lo = nums[i];
if (nums[i] > hi) hi = nums[i];
}
while (lo !== 0) {
const t = hi % lo;
hi = lo;
lo = t;
}
return hi;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays