Find Greatest Common Divisor of Array

Difficulty: Easy | Acceptance: 79.90% | Paid: No Topics: Array, Math, Number Theory

Given an integer array nums, return the greatest common divisor of the smallest number and the largest number in nums.

The greatest common divisor of two numbers is the largest positive integer that divides both numbers.

• Examples
• Constraints
• Built-in Functions
• Euclidean Algorithm (Iterative)
• Euclidean Algorithm (Recursive)
• Brute Force Search

Examples

Example 1:

Input: nums = [2,5,6,9,10]
Output: 2
Explanation:
The smallest number in nums is 2.
The largest number in nums is 10.
The greatest common divisor of 2 and 10 is 2.

Example 2:

Input: nums = [7,5,6,8,3]
Output: 1
Explanation:
The smallest number in nums is 3.
The largest number in nums is 8.
The greatest common divisor of 3 and 8 is 1.

Example 3:

Input: nums = [3,3]
Output: 3

Constraints

2 <= nums.length <= 1000
1 <= nums[i] <= 10⁹

Built-in Functions

Intuition Most modern programming languages provide standard library functions to find the minimum and maximum values in a collection, as well as calculate the Greatest Common Divisor (GCD) of two integers. Using these built-in functions results in the most concise and readable code.

Steps

• Find the minimum value in the array.
• Find the maximum value in the array.
• Use the language’s built-in GCD function to compute the result.

class Solution:
    def findGCD(self, nums: list[int]) -> int:
        import math
        return math.gcd(min(nums), max(nums))

Complexity

• Time: O(N) to find min and max, plus O(log(min(a, b))) for GCD.
• Space: O(1)
• Notes: Highly readable and leverages optimized standard library implementations.

Euclidean Algorithm (Iterative)

Intuition The Euclidean algorithm is an efficient method for computing the GCD. It is based on the principle that the GCD of two numbers also divides their difference. The iterative approach repeatedly replaces the larger number with the remainder of dividing the larger number by the smaller number until the remainder is 0.

Steps

• Identify the smallest and largest numbers in the array.
• Initialize a loop that continues while the larger number is not 0.
• In each iteration, calculate the remainder of the division of the larger number by the smaller number.
• Update the larger number to be the smaller number, and the smaller number to be the remainder.
• When the loop finishes, the non-zero number is the GCD.

class Solution:
    def findGCD(self, nums: list[int]) -> int:
        a = min(nums)
        b = max(nums)
        while b:
            a, b = b, a % b
        return a

Complexity

• Time: O(N) to find min/max, O(log(min(a, b))) for the GCD calculation.
• Space: O(1)
• Notes: Avoids recursion stack overhead, making it slightly safer for extremely large inputs (though not an issue here given constraints).

Euclidean Algorithm (Recursive)

Intuition This approach uses the same mathematical logic as the iterative Euclidean algorithm but implements it using recursion. The base case is when the second number becomes 0, at which point the first number is the GCD.

Steps

• Find the minimum and maximum values in the array.
• Call a recursive helper function with these two values.
• If the second value is 0, return the first value.
• Otherwise, return the result of the helper function called with the second value and the remainder of the first value divided by the second value.

class Solution:
    def findGCD(self, nums: list[int]) -> int:
        a = min(nums)
        b = max(nums)
        
        def gcd(x, y):
            if y == 0:
                return x
            return gcd(y, x % y)
            
        return gcd(a, b)

Complexity

• Time: O(N) to find min/max, O(log(min(a, b))) for the GCD calculation.
• Space: O(log(min(a, b))) due to the recursion stack.
• Notes: Elegant code, but iterative is generally preferred in production to avoid stack overflow on very deep recursions (unlikely here).

Brute Force Search

Intuition The GCD of two numbers must be less than or equal to the smaller of the two numbers. We can iterate backwards from the smaller number down to 1. The first number we find that divides both the minimum and maximum values evenly is the GCD.

Steps

• Find the minimum and maximum values in the array.
• Iterate from the minimum value down to 1.
• Check if the current iteration value divides both the minimum and maximum numbers without a remainder.
• If it does, return that value immediately.

class Solution:
    def findGCD(self, nums: list[int]) -> int:
        a = min(nums)
        b = max(nums)
        
        for i in range(a, 0, -1):
            if a % i == 0 and b % i == 0:
                return i
        return 1

Complexity

• Time: O(N) to find min/max, plus O(min(a, b)) for the search loop.
• Space: O(1)
• Notes: Inefficient for large numbers (e.g., if min is 10⁹ and GCD is 1, it loops 10⁹ times). Euclidean algorithm is preferred.