Scale Engineer

Find Greatest Common Divisor of Array

Easy
#1803Time: O(N log N + minVal)Space: O(log N) to O(N)
Patterns
MathNumber Theory
Data structures
Array

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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    }}

Complexity

Time

O(N log N + minVal)

Space

O(log N) to O(N)

Trade-offs

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.

Solutions

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); }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem