LeetCode 1979 - Find Greatest Common Divisor of Array

LeetCode Problem 1979

Difficulty: 🟢 Easy
Topics: Array, Math, Number Theory

Solution

Problem Understanding

The problem asks us to compute the greatest common divisor (GCD) of two specific values derived from the input array nums: the smallest element in the array and the largest element in the array.

In other words, we are not computing the GCD of all elements, nor are we looking for pairwise relationships across the array. We first reduce the array to two key representatives, the minimum and maximum values, and then compute the GCD of those two integers.

The input is an integer array nums with length between 2 and 1000, and each element is between 1 and 1000. The output is a single integer representing the GCD of min(nums) and max(nums).

These constraints are small, which suggests that an O(n) scan is sufficient for extracting the minimum and maximum values. The numbers themselves are also small (bounded by 1000), which guarantees that any standard GCD computation will be efficient.

Edge cases include arrays where all elements are identical, arrays where min and max are coprime, and arrays containing only two elements. A particularly important case is when min(nums) == max(nums), in which case the answer is that number itself, since gcd(x, x) = x.

Approaches

The brute-force approach would compute the minimum and maximum values, then determine their GCD by checking all possible divisors from the smaller of the two numbers down to 1. For each candidate divisor, we check whether it divides both numbers. The first valid divisor encountered is the answer. While correct, this is inefficient compared to using the Euclidean algorithm.

The key insight is that the problem reduces the entire array into just two numbers. Once we have the minimum and maximum, computing their GCD is a classic number theory problem best solved using the Euclidean algorithm, which repeatedly applies modulo reduction until reaching zero.

This reduces the problem from potentially examining many divisors to a logarithmic-time arithmetic process.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(min(a, b))	O(1)	Try all divisors of min(min, max) downward
Optimal	O(n + log(min(a, b)))	O(1)	Scan array for min/max, then Euclidean GCD

Algorithm Walkthrough

Initialize two variables min_val and max_val. Set both initially using the first element of the array. This ensures we have a valid starting comparison point.
Iterate through the array once. For each number, update min_val if the current number is smaller, and update max_val if the current number is larger. This step ensures we extract the two required representatives of the array in O(n) time.
After the scan completes, we now have the smallest and largest values in the array. These are the only values needed for the final computation.
Compute the GCD of min_val and max_val using the Euclidean algorithm. The Euclidean algorithm works by repeatedly replacing (a, b) with (b, a % b) until b becomes zero.
When b becomes zero, a holds the greatest common divisor, which is the final result.

Why it works

The correctness follows from the definition of the problem itself: the answer depends only on the smallest and largest elements in the array. The Euclidean algorithm guarantees that repeated modulo reduction preserves the GCD invariant, meaning gcd(a, b) = gcd(b, a % b) until termination.

Python Solution

from typing import List

class Solution:
    def findGCD(self, nums: List[int]) -> int:
        min_val = float('inf')
        max_val = float('-inf')
        
        for num in nums:
            if num < min_val:
                min_val = num
            if num > max_val:
                max_val = num
        
        def gcd(a: int, b: int) -> int:
            while b != 0:
                a, b = b, a % b
            return a
        
        return gcd(min_val, max_val)

The implementation first scans the array once to compute the minimum and maximum values. It then defines an inner helper function implementing the Euclidean algorithm. Finally, it returns the GCD of the two computed extremes.

Go Solution

func findGCD(nums []int) int {
    minVal := nums[0]
    maxVal := nums[0]
    
    for _, num := range nums {
        if num < minVal {
            minVal = num
        }
        if num > maxVal {
            maxVal = num
        }
    }
    
    gcd := func(a, b int) int {
        for b != 0 {
            a, b = b, a%b
        }
        return a
    }
    
    return gcd(minVal, maxVal)
}

In Go, we use a closure for the gcd function for simplicity. Slice iteration is done using range, and integer operations behave the same as in Python since the constraints are small and avoid overflow concerns.

Worked Examples

Example 1: nums = [2,5,6,9,10]

First pass to find extremes:

Step	num	min_val	max_val
init	-	2	2
1	2	2	2
2	5	2	5
3	6	2	6
4	9	2	9
5	10	2	10

Now compute gcd(2, 10):

(2, 10) → (10, 2)
(10, 2) → (2, 0)
Result = 2

Example 2: nums = [7,5,6,8,3]

Min/max extraction:

Step	num	min_val	max_val
init	-	7	7
1	7	7	7
2	5	5	7
3	6	5	7
4	8	5	8
5	3	3	8

Compute gcd(3, 8):

(3, 8) → (8, 3)
(8, 3) → (3, 2)
(3, 2) → (2, 1)
(2, 1) → (1, 0)
Result = 1

Example 3: nums = [3,3]

Min/max extraction:

Step	num	min_val	max_val
init	-	3	3
1	3	3	3
2	3	3	3

Compute gcd(3, 3) = 3 directly since values are equal.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + log(min(a, b)))	One pass to find min and max, then Euclidean GCD
Space	O(1)	Only constant extra variables used

The time complexity is dominated by the single linear scan of the array, followed by a logarithmic-time GCD computation.

Test Cases

assert Solution().findGCD([2,5,6,9,10]) == 2  # standard case
assert Solution().findGCD([7,5,6,8,3]) == 1   # coprime result
assert Solution().findGCD([3,3]) == 3         # all equal
assert Solution().findGCD([1,1000]) == 1      # extreme coprime bounds
assert Solution().findGCD([100,50,25]) == 25  # non-trivial gcd
assert Solution().findGCD([8,8,8,8]) == 8     # uniform array

Test	Why
[2,5,6,9,10]	validates typical mixed values
[7,5,6,8,3]	tests gcd producing 1
[3,3]	checks identical min/max
[1,1000]	boundary extremes
[100,50,25]	tests reduction structure
[8,8,8,8]	ensures stability under duplicates

Edge Cases

One important edge case is when all elements in the array are identical. In this case, both the minimum and maximum are the same value, and the GCD should trivially be that value. The implementation handles this naturally because the Euclidean algorithm returns a when a == b.

Another edge case is when the smallest value is 1. Since 1 divides every integer, the GCD of 1 and any number will always be 1. This ensures the algorithm quickly converges in such cases without any special handling.

A third edge case occurs when the minimum and maximum are coprime values, such as 3 and 8. In this case, the Euclidean algorithm will reduce the pair until reaching 1, correctly identifying that no larger common divisor exists.