Show problems as
Classic problem #1979EasyArrayMathNumber TheoryEuclidean AlgorithmGreatest Common Divisor

Find Greatest Common Divisor of Array

Real-world version: Sprocket Extremes Common Divisor
Tracked in this browser only
Read Find Greatest Common Divisor of Array on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A drawer holds a jumble of sprockets and nums[i] is the tooth count of the i-th one. The counts arrive in no particular order and two sprockets may well carry the same number of teeth.

A workshop jig needs the two extremes of the drawer: the sprocket with the fewest teeth and the sprocket with the most. Return the largest positive integer that divides both of those two tooth counts with nothing left over.

When one tooth count is both the smallest and the largest, the two extremes are the same value and that value is its own answer.

Examples

Example 1

Input
nums = [6, 10, 15]
Output
3

The extremes are 6 and 15. Both are divisible by 1 and by 3, and 3 is the larger of the two.

Example 2

Input
nums = [10, 4, 15]
Output
1

The extremes are 4 and 15, which share no divisor above 1.

Example 3

Input
nums = [8, 8]
Output
8

Both extremes are 8, and 8 divides itself.

Example 4

Input
nums = [14, 21, 28, 7]
Output
7

The fewest teeth is 7 and the most is 28; 7 divides 28 exactly, so 7 is the answer.

Constraints

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

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def sprocket_common_divisor(teeth: list[int]) -> int:
Java
public int sprocketCommonDivisor(int[] teeth)

More on the same topics