Find Greatest Common Divisor of Array: Min, Max, and Euclid

LeetCode 1979, Find Greatest Common Divisor of Array, asks you to find the greatest common divisor (GCD) of the smallest and largest numbers in an integer array. You are given an array of positive integers, and you need to return gcd(min(nums), max(nums)).

For example, given nums = [2, 5, 6, 9, 10], the smallest value is 2 and the largest is 10. The GCD of 2 and 10 is 2, so the answer is 2.

The approach: find the extremes, then apply Euclid

The problem breaks into two pieces:

1. Find the minimum and maximum of the array. A single pass through the array is enough.
2. Compute the GCD of those two values using the Euclidean algorithm.

The Euclidean algorithm works by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller. When the remainder hits zero, the other number is the GCD. It is one of the oldest known algorithms, and it runs in O(log(min(a, b))) time.

Here is how it works for GCD(10, 6):

• 10 % 6 = 4, so now compute GCD(6, 4)
• 6 % 4 = 2, so now compute GCD(4, 2)
• 4 % 2 = 0, remainder is zero, so GCD is 2

For GCD(10, 2), it finishes in one step: 10 % 2 = 0, so GCD is 2.

The code

from math import gcd

def findGCD(nums):
    return gcd(min(nums), max(nums))

That is the entire solution when you use Python's built-in gcd. If you want to implement the Euclidean algorithm yourself (which interviewers sometimes ask for):

def findGCD(nums):
    def euclidean_gcd(a, b):
        while b:
            a, b = b, a % b
        return a

    return euclidean_gcd(min(nums), max(nums))

Walk through what happens:

1. min(nums) scans the array once to find the smallest value.
2. max(nums) scans the array once to find the largest value.
3. euclidean_gcd repeatedly replaces (a, b) with (b, a % b) until b becomes zero. At that point, a holds the GCD.

You could also find the min and max in a single pass to avoid scanning the array twice, but the time complexity stays O(n) either way.

Visual walkthrough

Let's trace through the Euclidean algorithm step by step. The first example shows GCD(2, 10), which finishes immediately. The second example uses GCD(6, 10) to demonstrate multiple iterations of the algorithm.

The key loop is while b: a, b = b, a % b. Each iteration, b gets strictly smaller, so the loop always terminates. When b reaches zero, a is the answer.

Complexity analysis

The O(n) comes from scanning the array for the min and max. The O(log(min)) comes from the Euclidean algorithm, which halves the smaller operand roughly every two steps. For the array sizes LeetCode gives you, this is very fast.

Building blocks

This problem is built from two fundamental pieces that appear in many other problems.

Finding min and max

Scanning an array for its minimum or maximum is one of the most common building blocks in programming. You will use it in problems like finding the range of an array, normalizing values, or setting up a binary search range. Python gives you min() and max() as built-ins, but knowing how to do it manually (a single loop with a running tracker) is important for interviews.

The Euclidean algorithm

Computing the GCD of two numbers using repeated modulo is a building block that shows up whenever divisibility matters. Problems that use it include:

• X of a Kind in a Deck of Cards (LeetCode 914) computes the GCD of all card frequencies.
• Water Bottles (LeetCode 1518) uses division and remainder tracking.
• Any problem involving fractions, simplification, or least common multiples (since LCM(a, b) = a * b / GCD(a, b)).

The iterative version (while b: a, b = b, a % b) is worth memorizing. It is short, efficient, and comes up often enough that having it at your fingertips saves real time in interviews.

Edge cases

Array of length 2. The min and max are the two elements themselves. The GCD is computed directly. No special handling needed.

All elements are the same. If every element equals k, then min and max are both k, and GCD(k, k) = k.

Min divides max evenly. For example, [3, 9]. Since 9 % 3 = 0, the GCD equals the min (3). The algorithm finishes in one step.

Min and max are coprime. For example, [7, 10]. Since 7 and 10 share no common factor other than 1, the GCD is 1. The algorithm will run through a few iterations before reaching remainder zero.

Min equals 1. The GCD of 1 and any number is always 1. The algorithm returns immediately after one modulo operation.

From understanding to recall

This problem is labeled "easy," and the solution is short. But the details that matter, like writing the Euclidean algorithm loop from memory, remembering which variable holds the answer when b becomes zero, and knowing that while b is the correct termination condition, are exactly the kind of things that slip away if you only read about them once.

Spaced repetition turns these small details into permanent knowledge. You drill the Euclidean algorithm as its own brick, and you drill min/max scanning separately. After a few reps at increasing intervals, while b: a, b = b, a % b is something you type without thinking. When a harder problem needs GCD as a subroutine, you do not waste any mental energy on the building block.

Related posts

• X of a Kind in a Deck of Cards - Another easy problem that uses GCD as its core technique, applied to card frequencies
• Happy Number - An easy math problem where a simple number theory idea (cycle detection) powers the solution
• Contains Duplicate - The simplest array scanning problem, practicing the pattern of iterating through an array to check a property