# Find Greatest Common Divisor of Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-greatest-common-divisor-of-array)
Canonical: https://scaleengineer.com/dsa/problems/find-greatest-common-divisor-of-array
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array
---
## Problem
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.

**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
**Explanation:**
The smallest number in nums is 3.
The largest number in nums is 3.
The greatest common divisor of 3 and 3 is 3.

**Constraints:**

* `2 <= nums.length <= 1000`
* `1 <= nums[i] <= 1000`

# Approaches
## Sorting and Brute-Force GCD
This approach first sorts the input array to easily find the smallest and largest elements. Then, it uses a simple brute-force method to find the greatest common divisor (GCD) of these two numbers.
**Time:** O(N log N + minVal) · **Space:** O(log N) to O(N)
**Pros:** The logic is straightforward and easy to understand.; Implementation is simple, relying on a standard library sort function.
**Cons:** The `O(N log N)` time complexity for sorting makes this approach inefficient for large arrays.; The brute-force GCD calculation can be slow if the smallest number in the array is large.
### Explanation
The core idea is to simplify the problem of finding the min and max values by sorting the array first. Once sorted, the smallest element is at the beginning and the largest is at the end. After identifying these two numbers, we find their GCD. The GCD is found by iterating downwards from the smaller of the two numbers. The first integer we encounter that evenly divides both the smallest and largest numbers is their greatest common divisor.

```java
import java.util.Arrays;

class Solution {
    public int findGCD(int[] nums) {
        // Step 1: Sort the array
        Arrays.sort(nums);
        int smallest = nums[0];
        int largest = nums[nums.length - 1];

        // Step 2: Find GCD using brute-force iteration
        for (int i = smallest; i >= 1; i--) {
            if (smallest % i == 0 && largest % i == 0) {
                return i;
            }
        }
        return 1; // This line is technically unreachable given the constraints
    }
}
```
### Algorithm
- Sort the input array `nums` in non-decreasing order.
- The smallest number is `nums[0]` and the largest is `nums[nums.length - 1]`.
- Iterate from the smallest number down to 1.
- The first number `i` that divides both the smallest and largest numbers is the GCD.

## Single Pass and Brute-Force GCD
This approach improves upon the first one by finding the smallest and largest numbers in a single pass through the array, avoiding the costly sorting step. It still uses the brute-force method for calculating the GCD.
**Time:** O(N + minVal) · **Space:** O(1)
**Pros:** More efficient than the sorting approach because finding min/max is done in O(N) time.; Uses constant extra space.
**Cons:** While better than sorting, the brute-force GCD calculation is still not the most efficient method, especially for large numbers.
### Explanation
Instead of sorting the entire array, we can find the minimum and maximum elements more efficiently. We can iterate through the array just once, keeping track of the smallest and largest values seen so far. After this single pass, which takes linear time, we have the two numbers we need. The second part of the approach remains the same: a brute-force search for the GCD by checking all integers from the smallest number down to 1.

```java
class Solution {
    public int findGCD(int[] nums) {
        // Step 1: Find min and max in a single pass
        int minVal = nums[0];
        int maxVal = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < minVal) {
                minVal = nums[i];
            }
            if (nums[i] > maxVal) {
                maxVal = nums[i];
            }
        }

        // Step 2: Find GCD using brute-force iteration
        for (int i = minVal; i >= 1; i--) {
            if (minVal % i == 0 && maxVal % i == 0) {
                return i;
            }
        }
        return 1;
    }
}
```
### Algorithm
- Initialize `minVal` and `maxVal` with the first element of `nums`.
- Iterate through the `nums` array once to find the true minimum and maximum values.
- After finding `minVal` and `maxVal`, iterate from `i = minVal` down to `1`.
- The first `i` that evenly divides both `minVal` and `maxVal` is the GCD.

## Single Pass and Euclidean Algorithm
This is the most efficient approach. It finds the minimum and maximum elements in a single pass and then uses the highly efficient Euclidean algorithm to compute their greatest common divisor.
**Time:** O(N + log(minVal)) · **Space:** O(1)
**Pros:** Optimal time complexity, as both finding min/max and calculating GCD are done very efficiently.; Optimal constant space complexity.
**Cons:** Requires knowledge of the Euclidean algorithm, which might be slightly more complex than a simple loop.
### Explanation
This optimal solution combines the efficient single-pass method for finding the minimum and maximum values with the classic Euclidean algorithm for calculating the GCD. After determining the smallest and largest numbers in O(N) time, we apply the Euclidean algorithm. This algorithm is based on the principle that `gcd(a, b)` is the same as `gcd(b, a % b)`. We repeatedly apply this rule until the second number becomes 0. The first number is then the GCD. This method is significantly faster than brute-force for finding the GCD.

```java
class Solution {
    public int findGCD(int[] nums) {
        // Step 1: Find min and max in a single pass
        int minVal = Integer.MAX_VALUE;
        int maxVal = Integer.MIN_VALUE;
        for (int num : nums) {
            minVal = Math.min(minVal, num);
            maxVal = Math.max(maxVal, num);
        }

        // Step 2: Find GCD using the Euclidean Algorithm
        return gcd(minVal, maxVal);
    }

    // Helper function for Euclidean Algorithm (iterative)
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
```
### Algorithm
- Find the minimum (`minVal`) and maximum (`maxVal`) elements in the array by iterating through it once.
- Use the Euclidean algorithm to find the GCD of `minVal` and `maxVal`.
- The Euclidean algorithm repeatedly applies the logic `gcd(a, b) = gcd(b, a % b)` until the second number becomes 0.

# Solutions
### Java

```java
class Solution {
public
  int findGCD(int[] nums) {
    int a = 1, b = 1000;
    for (int x : nums) {
      a = Math.max(a, x);
      b = Math.min(b, x);
    }
    return gcd(a, b);
  }
private
  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

```

### CPP

```cpp
class Solution {
public:
  int findGCD(vector<int> &nums) {
    int a = *max_element(nums.begin(), nums.end());
    int b = *min_element(nums.begin(), nums.end());
    return gcd(a, b);
  }
};

```

### Python

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

```