Problem

Given an integer array nums, return****_thegreatest 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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


    
    
    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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


    
    
    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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


    
    
    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

Solution

Method 1 – Euclidean Algorithm

Intuition

The greatest common divisor (GCD) of two numbers is the largest number that divides both. For an array, since the problem asks for the GCD of the smallest and largest number, we only need to find the min and max, then compute their GCD using the classic Euclidean algorithm.

Approach

  1. Find the minimum value mn and maximum value mx in the array.
  2. Use the Euclidean algorithm to compute the GCD of mn and mx.
  3. Return the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int findGCD(vector<int>& nums) {
        int mn = *min_element(nums.begin(), nums.end());
        int mx = *max_element(nums.begin(), nums.end());
        while (mx) {
            int t = mn % mx;
            mn = mx;
            mx = t;
        }
        return mn;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func findGCD(nums []int) int {
    mn, mx := nums[0], nums[0]
    for _, v := range nums {
        if v < mn { mn = v }
        if v > mx { mx = v }
    }
    for mx != 0 {
        mn, mx = mx, mn%mx
    }
    return mn
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int findGCD(int[] nums) {
        int mn = nums[0], mx = nums[0];
        for (int v : nums) {
            if (v < mn) mn = v;
            if (v > mx) mx = v;
        }
        while (mx != 0) {
            int t = mn % mx;
            mn = mx;
            mx = t;
        }
        return mn;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun findGCD(nums: IntArray): Int {
        var mn = nums.minOrNull()!!
        var mx = nums.maxOrNull()!!
        while (mx != 0) {
            val t = mn % mx
            mn = mx
            mx = t
        }
        return mn
    }
}
1
2
3
4
5
6

class Solution:
    def findGCD(self, nums: list[int]) -> int:
        mn, mx = min(nums), max(nums)
        while mx:
            mn, mx = mx, mn % mx
        return mn
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn find_gcd(nums: Vec<i32>) -> i32 {
        let (mut mn, mut mx) = (*nums.iter().min().unwrap(), *nums.iter().max().unwrap());
        while mx != 0 {
            let t = mn % mx;
            mn = mx;
            mx = t;
        }
        mn
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    findGCD(nums: number[]): number {
        let mn = Math.min(...nums), mx = Math.max(...nums);
        while (mx !== 0) {
            [mn, mx] = [mx, mn % mx];
        }
        return mn;
    }
}

Complexity

  • ⏰ Time complexity: O(n + log(max)), where n is the length of nums (for finding min and max), and log(max) for the GCD computation.
  • 🧺 Space complexity: O(1), as only a few variables are used.