Find Greatest Common Divisor of Array
EasyPrompt
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 <= 10001 <= 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
numsin non-decreasing order. - The smallest number is
nums[0]and the largest isnums[nums.length - 1]. - Iterate from the smallest number down to 1.
- The first number
ithat 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.
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.
Algorithm
- Initialize
minValandmaxValwith the first element ofnums. - Iterate through the
numsarray once to find the true minimum and maximum values. - After finding
minValandmaxVal, iterate fromi = minValdown to1. - The first
ithat evenly divides bothminValandmaxValis the GCD.
Walkthrough
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.
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; }}Complexity
Time
O(N + minVal)
Space
O(1)
Trade-offs
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.
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.
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
minValandmaxVal. - The Euclidean algorithm repeatedly applies the logic
gcd(a, b) = gcd(b, a % b)until the second number becomes 0.
Walkthrough
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.
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; }}Complexity
Time
O(N + log(minVal))
Space
O(1)
Trade-offs
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.
Solutions
Solution
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); }}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); }};class Solution: def findGCD(self, nums: List[int]) -> int: return gcd(max(nums), min(nums))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.