Solution Explanation: Finding the Greatest Common Divisor (GCD) of an Array

The problem asks to find the greatest common divisor (GCD) of the smallest and largest numbers within a given integer array. The solution involves these steps:

1. Find Minimum and Maximum: Iterate through the input array nums to identify the smallest and largest numbers. This can be efficiently done using built-in functions like min() and max() in most languages.

2. Calculate GCD: Once the minimum and maximum values are found, compute their GCD. The Euclidean algorithm is a highly efficient method for this calculation. The Euclidean algorithm recursively applies the modulo operator until the remainder is zero. The last non-zero remainder is the GCD.

Time and Space Complexity Analysis

• Time Complexity: The algorithm's time complexity is dominated by two parts:

  • Finding the minimum and maximum elements in the array takes O(n) time, where n is the length of the array.
  • The Euclidean algorithm for GCD calculation has a time complexity that is logarithmic in the size of the input numbers (approximately O(log(min(a, b))), where a and b are the minimum and maximum numbers). In this case, since the input numbers are constrained to be between 1 and 1000, the GCD computation takes relatively constant time.

  Therefore, the overall time complexity is O(n), linear with respect to the size of the input array.

• Space Complexity: The algorithm uses a constant amount of extra space to store the minimum, maximum values, and temporary variables during the GCD computation. Hence, the space complexity is O(1), constant.

Code Implementations (with explanations)

The following code snippets demonstrate the solution in several popular programming languages. The core logic remains consistent across all implementations.

Python:

import math
 
def findGCD(nums):
    """
    Finds the greatest common divisor of the smallest and largest numbers in nums.
 
    Args:
        nums: A list of integers.
 
    Returns:
        The greatest common divisor.
    """
    min_num = min(nums)
    max_num = max(nums)
    return math.gcd(min_num, max_num) # Python's built-in GCD function
 

Java:

class Solution {
    public int findGCD(int[] nums) {
        int min = nums[0];
        int max = nums[0];
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        return gcd(min, max);
    }
 
    private int gcd(int a, int b) { // Euclidean algorithm
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

C++:

#include <numeric> // for std::gcd
#include <algorithm> // for std::min_element, std::max_element
 
class Solution {
public:
    int findGCD(vector<int>& nums) {
        int min_num = *std::min_element(nums.begin(), nums.end());
        int max_num = *std::max_element(nums.begin(), nums.end());
        return std::gcd(min_num, max_num); // C++17's built-in GCD function
 
    }
};

JavaScript:

/**
 * @param {number[]} nums
 * @return {number}
 */
const findGCD = (nums) => {
    let min = nums[0];
    let max = nums[0];
    for (let i = 1; i < nums.length; i++) {
        min = Math.min(min, nums[i]);
        max = Math.max(max, nums[i]);
    }
    return gcd(min, max);
};
 
const gcd = (a, b) => { //Euclidean Algorithm
    if (b === 0) {
        return a;
    }
    return gcd(b, a % b);
};

These examples show how to implement the solution efficiently and clearly in different languages. The choice of language may affect minor details (e.g., the availability of built-in GCD functions), but the underlying algorithmic approach remains the same.