Find Greatest Common Divisor of Array

Given an integer array nums, return the greatest common divisor of the smallest number and largest number in nums. The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers. For example:

• nums = [2,5,6,9,10] should return 2 because the smallest number is 2, the largest is 10, and the GCD(2, 10) = 2.
• nums = [7,5,6,8,3] should return 1 because the smallest number is 3, the largest is 8, and the GCD(3, 8) = 1.
• nums = [3,3] should return 3 because the smallest number is 3, the largest is 3, and the GCD(3, 3) = 3.

Write a function to implement this with the constraint that 2 <= nums.length <= 1000 and 1 <= nums[i] <= 1000.

## Greatest Common Divisor of Smallest and Largest Number in Array

This problem requires us to find the greatest common divisor (GCD) of the smallest and largest numbers within a given integer array. Let's explore a few approaches to solve this problem.

### 1. Naive Approach

The most straightforward approach is to first find the smallest and largest numbers in the array, and then iterate from 1 up to the smaller of these two numbers, checking for the largest number that divides both without any remainder. This approach is easy to understand but not the most efficient.

```python
def gcd_naive(a, b):
    smaller = min(a, b)
    gcd = 1
    for i in range(1, smaller + 1):
        if a % i == 0 and b % i == 0:
            gcd = i
    return gcd

def find_gcd_of_min_max_naive(nums):
    smallest = min(nums)
    largest = max(nums)
    return gcd_naive(smallest, largest)

# Example usage:
nums = [2, 5, 6, 9, 10]
result = find_gcd_of_min_max_naive(nums)
print(f"The GCD of the smallest and largest number is: {result}")

2. Optimal Approach: Euclidean Algorithm

A more efficient approach is to use the Euclidean algorithm to find the GCD. The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. This can be optimized further by using the modulo operator.

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

def find_gcd_of_min_max(nums):
    smallest = min(nums)
    largest = max(nums)
    return gcd_euclidean(smallest, largest)

# Example usage:
nums = [2, 5, 6, 9, 10]
result = find_gcd_of_min_max(nums)
print(f"The GCD of the smallest and largest number is: {result}")

Big(O) Run-time Analysis

• Naive Approach: The time complexity is O(min(smallest, largest)), where smallest and largest are the smallest and largest numbers in the array. This is because, in the worst case, the loop iterates up to the smaller of the two numbers.
• Euclidean Algorithm: The time complexity is O(log(min(a, b))), where a and b are the two numbers. The Euclidean algorithm reduces the numbers significantly faster, leading to a logarithmic time complexity.

Big(O) Space Usage Analysis

• Both the naive and Euclidean algorithm approaches have a space complexity of O(1) because they use a constant amount of extra space regardless of the input size. Only a few variables are used to store the smallest, largest, and GCD values.

Edge Cases and Considerations

1. Empty Array: If the input array is empty, we should raise an exception or return a default value (e.g., 0 or 1) based on the problem's requirements.
2. Single Element Array: If the array contains only one element, the GCD should be the element itself.
3. Array with Identical Elements: If all elements in the array are the same, the GCD is simply that element.
4. Negative Numbers: The GCD is typically defined for positive integers. If negative numbers are present, you can take the absolute value before calculating the GCD, as gcd(a, b) = gcd(|a|, |b|).
5. Zero: If either the smallest or largest number is zero, the GCD is the non-zero number. If both are zero, the GCD is typically defined as zero.

Here's the updated code considering some edge cases:

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

def find_gcd_of_min_max_robust(nums):
    if not nums:
        return 0  # Or raise an exception: raise ValueError("Array cannot be empty")
    
    smallest = min(nums)
    largest = max(nums)
    
    if smallest == 0 and largest == 0:
        return 0
        
    return gcd_euclidean(abs(smallest), abs(largest))

# Example usage:
nums = [2, 5, 6, 9, 10]
result = find_gcd_of_min_max_robust(nums)
print(f"The GCD of the smallest and largest number is: {result}")

nums = []
result = find_gcd_of_min_max_robust(nums)
print(f"The GCD of the smallest and largest number is: {result}")

nums = [5,5,5,5]
result = find_gcd_of_min_max_robust(nums)
print(f"The GCD of the smallest and largest number is: {result}")

By using the Euclidean algorithm and handling edge cases appropriately, we can efficiently and robustly find the GCD of the smallest and largest numbers in the given array.