Find Greatest Common Divisor of Array — LeetCode Daily Python Solution (the trick nobody sees)

Introduction

Math-based problems have a reputation for being either trivially easy or secretly tricky, and Find Greatest Common Divisor of Array sits right at that intersection. On the surface it looks like a simple array question. Underneath, it's testing something more specific: do you actually understand what GCD means, and can you spot when a problem is quietly simplifying itself for you.

This kind of question shows up in early interview rounds at companies like Amazon and Google, not because GCD itself is hard, but because it's a fast way to check whether you reach for the right tool instead of reinventing math from scratch. GCD logic isn't just an interview trick either — it powers fraction simplification, cryptographic key generation, and scheduling systems that need to sync recurring events. Small concept, wide reach.

By the end of this article, you'll know why this "array problem" is really a two-number problem in disguise, how Euclid's algorithm makes math.gcd() fast, and how to write a clean, interview-ready Python solution.

Problem Overview

You're given an array of positive integers. Your task is to find the greatest common divisor (GCD) of the smallest and largest numbers in that array.

To be precise about the definition: the GCD of two numbers is the largest number that divides both of them evenly, with no remainder.

The key detail — and the part that trips people up — is that the problem only cares about the smallest and largest values in the array. Every other number is irrelevant to the final answer.

Example

Suppose we have this array:

nums = [2, 5, 6, 9, 10]

Step 1: Find the minimum and maximum.

• Minimum: 2
• Maximum: 10

Step 2: Find the GCD of 2 and 10.

• The divisors of 2 are: 1, 2
• The divisors of 10 are: 1, 2, 5, 10
• The largest number appearing in both lists is 2.

Output: 2

The numbers 5, 6, and 9 never factor into the calculation at all. They exist in the array, but they're bystanders.

Intuition

The first instinct many people have is to treat this as an array problem — maybe compute the GCD of every pair, or reduce the whole array pairwise. That instinct is understandable but wasteful, and the problem statement is quietly telling you not to do that.

Re-read the requirement: "the GCD of the smallest and largest number." That phrasing isn't decoration — it's the entire algorithm. The problem has already told you which two numbers matter. Your job isn't to search for them; it's to notice that you were told.

Once you see that, this stops being an "array of GCDs" problem and becomes the classic two-number GCD problem wearing an array costume. That reframing is the whole trick. An experienced engineer doesn't start writing loops here — they start by rereading the problem statement for hints about which values are actually load-bearing.

From there, the only remaining question is: how do you compute GCD of two numbers efficiently? That's where Euclid's algorithm comes in — an ancient technique where you repeatedly replace the larger number with the remainder of dividing the two numbers, until nothing's left to divide. The last nonzero remainder is your answer. It shrinks the problem fast, which is why it's the standard approach used inside math.gcd().

Brute Force Solution

Idea: Instead of using Euclid's algorithm, count downward from the smaller of the two numbers and stop at the first value that divides both numbers evenly.

Algorithm:

1. Find min and max of the array.
2. Starting from min, count down to 1.
3. For each candidate i, check if both min % i == 0 and max % i == 0.
4. Return the first i that satisfies both conditions.

Advantages:

• Intuitive and easy to explain out loud in an interview if you blank on math.gcd().
• No need to remember Euclid's algorithm or any library function.

Disadvantages:

• Slower for large numbers.
• More code, and more room for off-by-one mistakes under interview pressure.

Time Complexity: O(min(a, b)) — in the worst case, you check every number from the smaller value down to 1.

Space Complexity: O(1) — no extra data structures used.

Optimal Solution

The optimal approach has two parts, and both lean on tools that are already sitting in Python's standard library.

Step 1 — Reduce the array to two numbers. Use Python's built-in min() and max() functions to pull out the smallest and largest values. These are implemented in C and already optimized — there's no reason to hand-write a scanning loop to find them yourself.

Step 2 — Compute GCD with Euclid's algorithm. Python's math module ships a battle-tested gcd() function. Instead of brute-force checking divisors, it uses Euclid's algorithm:

Step	a	b	a % b
1	10	2	0

Since 10 % 2 == 0, the algorithm stops immediately — b (which is 2) is the GCD.

For a case where it takes more steps, consider GCD(48, 18):

Step	a	b	a % b
1	48	18	12
2	18	12	6
3	12	6	0

The last nonzero remainder is 6, so GCD(48, 18) = 6. Notice how fast this shrinks — that speed is exactly why Euclid's algorithm beats brute force for large inputs.

Python Code

import math
from typing import List


def find_gcd(nums: List[int]) -> int:
    """Return the GCD of the smallest and largest values in nums."""
    return math.gcd(min(nums), max(nums))

Code Walkthrough

• min(nums) scans the array once and returns the smallest value.
• max(nums) scans the array once and returns the largest value.
• math.gcd(a, b) runs Euclid's algorithm internally and returns the greatest common divisor of the two values.
• The whole function is a single return statement — there's no reason to introduce intermediate variables or manual loops here.

Dry Run

Input: nums = [2, 5, 6, 9, 10]

1. min(nums) → 2
2. max(nums) → 10
3. math.gcd(2, 10):
   • 10 % 2 == 0, so the loop stops immediately.
   • Result: 2
4. Return 2.

Complexity Analysis

Time Complexity: O(n + log(min(a, b)))

• Finding min and max each take O(n) since you must look at every element once.
• math.gcd() runs in O(log(min(a, b))) because Euclid's algorithm shrinks the problem roughly like a binary search — each step cuts the remainder down dramatically.
• Overall, the array scan dominates for large arrays, but the GCD step itself is extremely fast.

Space Complexity: O(1) — no additional data structures are allocated; only a few scalar values are tracked.

This is correct because neither min(), max(), nor math.gcd() allocate memory proportional to the input — they all operate in constant extra space.

Alternative Solutions

The brute force divisor search covered earlier is a fair fallback if math.gcd() slips your mind mid-interview. It's worth saying out loud, then improving on:

Approach	Time Complexity	Space	When to use
Euclid's algorithm (math.gcd)	O(log(min(a,b)))	O(1)	Always preferred — standard, fast, correct
Brute force divisor search	O(min(a,b))	O(1)	Fallback if you forget the library function

For large numbers, Euclid's approach wins by a wide margin, since it shrinks the problem logarithmically instead of linearly.

Edge Cases

• Empty input: Not valid per constraints — the problem guarantees at least one element, but always confirm array length assumptions in an interview.
• Two elements only: min and max still work correctly with just two values.
• All duplicates (e.g., [2, 2]): min and max are the same number, so you're computing GCD of a number with itself, which is always that number.
• One number divides the other (e.g., [2, 10]): The smaller number is the answer, and Euclid's algorithm terminates in a single step.
• Large values: Euclid's algorithm keeps performance fast even as numbers grow, unlike brute force which scales linearly with the smaller value.

Common Mistakes

1. Computing GCD across the entire array instead of just min and max, which wastes time and adds unnecessary complexity.
2. Hand-writing a scanning loop for min/max instead of using Python's optimized built-ins.
3. Forgetting that math.gcd() requires non-negative integers — passing negative numbers can produce unexpected results depending on Python version.
4. Writing a brute force divisor search with an off-by-one error in the loop bounds.
5. Assuming duplicates need special-case handling, when the formula already handles them correctly.
6. Not testing with a two-element array, which can expose faulty assumptions about array size.

Interview Questions

• What is Euclid's algorithm, and can you explain why it's efficient?
• How would you compute the GCD of more than two numbers?
• What's the difference between GCD and LCM, and how are they related?
• Can you implement gcd() manually without using the math module?
• How does GCD relate to the Extended Euclidean Algorithm used in cryptography?

Similar Problems

• LeetCode 1979 — Find Greatest Common Divisor of Array: this exact problem.
• LeetCode 1071 — Greatest Common Divisor of Strings: applies the same GCD intuition to string patterns instead of numbers.
• LeetCode 878 — Nth Magical Number: uses GCD and LCM together to solve a counting problem.
• LeetCode 365 — Water and Jug Problem: relies on GCD theory (Bézout's identity) to determine reachable states.

Key Takeaways

• Always read the problem statement carefully — it often tells you exactly which values matter, like it does here with "smallest and largest."
• Reach for standard library functions like math.gcd(), min(), and max() before writing manual implementations.
• Euclid's algorithm is fast because it shrinks the problem logarithmically, not linearly.
• Brute force is a legitimate fallback to mention in an interview, but always follow it up with the optimal approach.
• Small math concepts like GCD show up in real systems — cryptography, fraction simplification, and event scheduling all lean on it.

Watch the Video

For a full visual walkthrough of this problem, including the step-by-step trace of Euclid's algorithm and a pause-and-predict challenge, check out the video here: {LINK}

About the Series

This breakdown is part of the Daily Python LeetCode series, where one problem gets solved, explained, and broken down in Python every single day. The goal isn't just to get to a working answer — it's to build the intuition that lets you recognize similar patterns instantly in future interviews.

Call To Action

If this helped clarify how to think about GCD problems, subscribe on YouTube for daily walkthroughs, and subscribe to the Substack newsletter for the written breakdowns delivered straight to your inbox. Drop a comment with which problem you'd like solved next, and share this with a friend prepping for interviews.

---

def find_gcd(nums):
    lo, hi = min(nums), max(nums)
    for d in range(lo, 0, -1):
        if lo % d == 0 and hi % d == 0:
            return d