Problem Description

You are given an integer array nums. Your task is to find the greatest common divisor (GCD) between the smallest and largest numbers in the array.

The greatest common divisor of two numbers is the largest positive integer that divides both numbers evenly (with no remainder).

For example:

• If nums = [2, 5, 6, 9, 10], the smallest number is 2 and the largest is 10. The GCD of 2 and 10 is 2.
• If nums = [7, 5, 6, 8, 3], the smallest number is 3 and the largest is 8. The GCD of 3 and 8 is 1.

The solution involves:

1. Finding the minimum value in the array using min(nums)
2. Finding the maximum value in the array using max(nums)
3. Computing the GCD of these two values using the built-in gcd() function

The gcd() function from Python's math module efficiently calculates the greatest common divisor using the Euclidean algorithm. The time complexity is O(n) for finding min/max values, and O(log(min(a,b))) for computing the GCD where a and b are the two numbers.

Intuition

The problem asks for the GCD of two specific numbers from the array - the smallest and the largest. This immediately tells us we don't need to consider all elements in the array, just these two extremes.

Why just these two? The problem explicitly states we need the GCD of the minimum and maximum values. This simplifies our task significantly - instead of dealing with the entire array, we reduce it to a two-number GCD problem.

The key insight is that this is really two separate sub-problems:

1. Finding the extremes (min and max) in the array
2. Finding the GCD of two numbers

For finding extremes, we can simply scan through the array once. Python provides built-in min() and max() functions that do exactly this.

For finding the GCD, we could implement our own algorithm (like the Euclidean algorithm where we repeatedly apply gcd(a, b) = gcd(b, a % b) until b becomes 0), but Python's math module already provides an optimized gcd() function.

The beauty of this approach is its directness - we identify exactly what we need (min, max, and their GCD) and use the most straightforward tools available to get them. There's no need for sorting the entire array or checking GCDs of multiple pairs. We go straight to the answer by focusing only on the two values that matter.

Learn more about Math patterns.

Solution Approach

The solution follows a straightforward simulation approach as mentioned in the reference. We directly implement what the problem asks for in three simple steps:

1. Find the maximum value in the array: We use Python's built-in max() function which iterates through the array once to find the largest element. This takes O(n) time where n is the length of the array.

2. Find the minimum value in the array: Similarly, we use Python's built-in min() function to find the smallest element. This also takes O(n) time.

3. Calculate the GCD: We use the gcd() function from Python's math module to compute the greatest common divisor of the max and min values found in steps 1 and 2.

The implementation is remarkably concise:

return gcd(max(nums), min(nums))

This single line:

• Calls max(nums) to get the largest value
• Calls min(nums) to get the smallest value
• Passes both values to gcd() to compute their greatest common divisor
• Returns the result

The gcd() function internally uses the Euclidean algorithm, which works by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller, until one number becomes 0. The other number at that point is the GCD.

For example, if we have gcd(10, 2):

• 10 % 2 = 0, so the GCD is 2

Or for gcd(8, 3):

• 8 % 3 = 2
• 3 % 2 = 1
• 2 % 1 = 0, so the GCD is 1

The time complexity is O(n + log(min(a,b))) where n is the array length (for finding min/max) and a, b are the two numbers being processed for GCD. The space complexity is O(1) as we only store two values regardless of input size.

Example Walkthrough

Let's walk through the solution with a concrete example: nums = [12, 8, 3, 14, 6]

Step 1: Find the minimum value

• Scan through the array: 12, 8, 3, 14, 6
• The minimum value is 3

Step 2: Find the maximum value

• Scan through the same array: 12, 8, 3, 14, 6
• The maximum value is 14

Step 3: Calculate GCD(14, 3) Using the Euclidean algorithm:

• 14 % 3 = 2 (14 = 3 × 4 + 2)
• Now compute GCD(3, 2)
• 3 % 2 = 1 (3 = 2 × 1 + 1)
• Now compute GCD(2, 1)
• 2 % 1 = 0 (2 = 1 × 2 + 0)
• When we reach 0, the other number (1) is our GCD

Result: GCD(3, 14) = 1

Let's verify with another example: nums = [20, 40, 10, 30]

Step 1: Find minimum → 10 Step 2: Find maximum → 40 Step 3: Calculate GCD(40, 10)

• 40 % 10 = 0 (40 = 10 × 4 + 0)
• When remainder is 0, the divisor (10) is our GCD

Result: GCD(10, 40) = 10

The complete solution in code would be:

from math import gcd

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

This elegantly combines all three steps into a single line, letting Python's built-in functions handle the heavy lifting while maintaining clarity and efficiency.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + log(min(a, b))), where n is the length of the array nums, a = max(nums), and b = min(nums).

• Finding the maximum element: O(n) - requires traversing the entire array once
• Finding the minimum element: O(n) - requires traversing the entire array once
• Computing GCD using Euclidean algorithm: O(log(min(a, b))) where a and b are the two numbers

Since the GCD computation time is typically much smaller than n for practical inputs, the overall time complexity is dominated by O(n).

Space Complexity: O(1)

• The max() and min() functions use constant extra space
• The gcd() function (Euclidean algorithm) uses constant extra space for its internal computations
• No additional data structures are created that scale with input size

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Edge Cases with Single Element Arrays

While the provided solution works correctly for arrays with multiple elements, a common pitfall is not considering what happens when the array contains only one element. In this case, both the minimum and maximum values are the same number.

Issue: When nums = [5], both min and max are 5, so we're computing gcd(5, 5).

Why it's actually fine: The GCD of a number with itself is the number itself, so gcd(5, 5) = 5, which is mathematically correct. The provided solution handles this case properly without any special logic needed.

2. Assuming Import of gcd is Automatic

A common mistake is forgetting to import the gcd function from the math module, leading to a NameError.

Incorrect approach:

class Solution:
    def findGCD(self, nums: List[int]) -> int:
        return gcd(max(nums), min(nums))  # NameError: name 'gcd' is not defined

Correct approach:

from math import gcd  # Don't forget this import!

class Solution:
    def findGCD(self, nums: List[int]) -> int:
        return gcd(max(nums), min(nums))

3. Implementing Custom GCD Without Understanding Edge Cases

Some developers might try to implement their own GCD function without fully understanding the algorithm, leading to infinite loops or incorrect results.

Problematic custom implementation:

def custom_gcd(a, b):
    while b:
        a, b = b, a % b
    return a

class Solution:
    def findGCD(self, nums: List[int]) -> int:
        return custom_gcd(max(nums), min(nums))

Issue: While this implementation is actually correct, developers might make mistakes like:

• Not handling the case where b is initially larger than a
• Using a / b instead of a % b (division instead of modulo)
• Not updating both variables correctly in the loop

Better approach: Use the built-in math.gcd() which is thoroughly tested and optimized.

4. Unnecessary Multiple Passes Through the Array

Some might make multiple passes through the array unnecessarily:

Inefficient approach:

class Solution:
    def findGCD(self, nums: List[int]) -> int:
        nums.sort()  # O(n log n) - unnecessary sorting!
        return gcd(nums[-1], nums[0])

Why it's inefficient: Sorting takes O(n log n) time when we only need O(n) to find min and max values.

Optimal approach: Use min() and max() functions which each make a single O(n) pass through the array.