Skip to content

Practice Find Greatest Common Divisor of Array

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Easy#1979
LeetCode Problem

Find Greatest Common Divisor of Array

Problem Statement

Given an integer array nums, return the greatest common divisor of the smallest number and largest number in nums. The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.

Source: Find Greatest Common Divisor of Array on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
nums = [2,5,6,9,10]
Output
2
Explanation

The smallest value is 2 and the largest is 10. Their common positive divisors are 1 and 2, so the greatest is 2. Only these two extreme values determine the requested result. In particular, 2 does not divide the array's 5 or 9, but that does not disqualify it. Computing the GCD of every array element would give 1 and would answer a different question.

# Example 2

Input
nums = [7,5,6,8,3]
Output
1
Explanation

The extreme values are 3 and 8. Euclid's algorithm gives 8 % 3 = 2, 3 % 2 = 1 and 2 % 1 = 0; the last nonzero remainder is 1. Hence their only common positive divisor is 1, and the answer is 1. The array is unsorted, so its first and last entries, 7 and 3, are not the pair specified by the problem; find the minimum and maximum first.

# Example 3

Input
nums = [3,3]
Output
3
Explanation

Both the minimum and maximum are 3. Every positive divisor of 3 divides both extreme values, and the greatest is 3 itself, so return 3. The two values used by the calculation are allowed to be equal. There is no requirement to find two distinct numeric values, and repeated entries do not change the result.

Constraints

2 <= nums.length <= 1000
1 <= nums[i] <= 1000

How to solve Find Greatest Common Divisor of Array

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

Only two numbers matter, the minimum and the maximum, so one pass to find them followed by the Euclidean algorithm settles it; every other element is irrelevant.

Why brute force is not enough

Testing every candidate divisor from the smaller extreme downward until one divides both takes O(min) steps, up to 1000 here, which passes but is far slower than the logarithmic Euclidean descent; computing the GCD of the entire array answers a different question and returns 1 on example 1.

Approach

  1. Scan nums once while tracking the smallest and largest values seen; do not sort, since only the extremes are needed.
  2. Apply the Euclidean algorithm to the pair: repeatedly replace the larger number by the remainder of the larger divided by the smaller.
  3. The invariant is that the GCD of the pair is unchanged by this replacement, so when the remainder reaches zero the other number is the answer.
  4. Return that value; when the minimum equals the maximum the loop ends immediately with that value.

Walkthrough of Example 2

nums = [7,5,6,8,3] → 1

  1. The minimum of [7,5,6,8,3] is 3 and the maximum is 8.
  2. 8 mod 3 = 2, so the pair becomes (3, 2).
  3. 3 mod 2 = 1, giving (2, 1); then 2 mod 1 = 0, so the last nonzero value is 1.
  4. Return 1.

Time and space

Time O(n + log(max)) · Space O(1). n is the array length for the extremes scan, and the Euclidean algorithm on values at most 1000 takes a logarithmic number of remainder steps; only a few scalars are stored.

Interview pitfalls

  • Taking the GCD of all elements instead of only the minimum and maximum.
  • Using the first and last elements as the extremes without scanning; example 2 is unsorted.
  • Writing the Euclidean step with repeated subtraction instead of modulo, which is correct but linear in the values.
  • Forgetting the minimum equals maximum case, where the answer is that value itself, as in example 3.
  • Sorting the array just to find the extremes, adding an unnecessary logarithmic factor.

Follow-up questions interviewers ask

  • How would you compute the GCD of the whole array, and why can you stop early once the running GCD reaches 1?
  • How does the extended Euclidean algorithm recover coefficients expressing the GCD as a combination of the two numbers?
  • If the array receives insertions and deletions online, how would you maintain the minimum and maximum efficiently?

Further reading on the technique: Euclidean algorithm

Related LeetCode Problems

Practice more problems similar to Find Greatest Common Divisor of Array.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.