0339EasyArrayMathNumber TheoryEuclidean AlgorithmGreatest Common Divisor

Sprocket Extremes Common Divisor

Tracked in this browser only

Trains the technique from

LeetCode 1979Find Greatest Common Divisor of Array

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def sprocket_common_divisor(teeth: list[int]) -> int:

Java

public int sprocketCommonDivisor(int[] teeth)

The intended approach

Time O(n + log(max tooth count))Space O(1)

One walk over the drawer records the smallest and the largest tooth count. Those two values are then reduced with repeated remainder taking: replace the pair by the smaller value and the remainder of the larger divided by it until the remainder is zero, at which point the surviving value is the divisor asked for.

Pythonentry point: sprocket_common_divisor

def sprocket_common_divisor(teeth):
    # One pass for the extremes, then the subtraction-free Euclid loop.
    # Time O(n + log(max teeth)). Space O(1).
    fewest = teeth[0]
    most = teeth[0]
    for t in teeth:
        if t < fewest:
            fewest = t
        if t > most:
            most = t
    a = most
    b = fewest
    while b:
        a, b = b, a % b
    return a

The obvious version

Try every divisor from the smaller extreme downwards and return the first one that divides both.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_sprocket_common_divisor(teeth):
    fewest = min(teeth)
    most = max(teeth)
    d = fewest
    while d > 1:
        if fewest % d == 0 and most % d == 0:
            return d
        d -= 1
    return 1

How this problem was checked

Reference solution executed against 9 test cases — 9 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in