Find Greatest Common Divisor of Array - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: Given an integer array nums, return the greatest common divisor (GCD) of the smallest and largest numbers in the array. The key observation is that the GCD of the entire array reduces to the GCD of min(nums) and max(nums).
The task splits into two parts: first scan the array to find the minimum and maximum values, then compute their GCD using the Euclidean algorithm. This problem combines simple array traversal with a classic number theory technique.
Approach 1: Iterative Euclidean Algorithm (O(n + log M) time, O(1) space)
Start by iterating through the array once to compute minVal and maxVal. This takes O(n) time and constant space. After that, compute the GCD using the iterative Euclidean algorithm: repeatedly replace (a, b) with (b, a % b) until b == 0. The remaining value a is the GCD.
The Euclidean algorithm works because the GCD of two numbers does not change when replacing the larger number with its remainder after division. Each iteration reduces the size of the numbers quickly, giving a time complexity of O(log M), where M is the larger number. This approach is efficient, avoids recursion overhead, and works well in languages where iterative loops are preferred.
Approach 2: Recursive Euclidean Algorithm (O(n + log M) time, O(log M) space)
This approach uses the same mathematical idea but expresses the Euclidean algorithm recursively. After computing minVal and maxVal from the array, define a recursive function gcd(a, b). If b == 0, return a. Otherwise return gcd(b, a % b).
Each recursive call reduces the problem size exactly like the iterative version. The recursion depth is at most O(log M), which means the extra stack space is also logarithmic. This version is often considered more elegant and mirrors the mathematical definition of the Euclidean algorithm closely.
Both approaches rely on fundamental concepts from math and number theory. The only array operation needed is a single pass to identify the smallest and largest elements.
Recommended for interviews: The iterative Euclidean algorithm is typically preferred. Interviewers expect you to recognize that only the minimum and maximum values matter, then apply the Euclidean algorithm to compute the GCD efficiently. Mentioning both iterative and recursive forms demonstrates understanding of the underlying number theory, but the iterative version is slightly more practical in production code.
Approach 1: Approach 1: Iterative Euclidean Algorithm
This approach involves first identifying the smallest and largest numbers in the array, then using the iterative Euclidean algorithm to find their GCD.
The code follows the Euclidean algorithm to compute the GCD of two numbers by iteratively applying the formula a = b and b = a % b until b becomes 0. The minimum and maximum values are derived from the array to apply this algorithm.
Complexity
Time Complexity: O(log(min(a, b)))
Space Complexity: O(1)
Approach 2: Approach 2: Recursive Euclidean Algorithm
In this approach, we use the recursive method to implement the Euclidean algorithm for finding the GCD. Identify the minimum and maximum values in the array, then recursively apply the GCD calculation.
This C code takes a recursive approach to calculate the GCD using Euclidean method, recursively solving for gcd(b, a % b) until b is zero.
Complexity
Time Complexity: O(log(min(a, b)))
Space Complexity: O(1)
Approach 3: Simulation
We can simulate according to the problem description. First, find the maximum and minimum values in the array nums, then find the greatest common divisor of the maximum and minimum values.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Euclidean Algorithm | Time Complexity: O(log(min(a, b))) |
| Approach 2: Recursive Euclidean Algorithm | Time Complexity: O(log(min(a, b))) |
| Simulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Euclidean Algorithm | O(n + log M) | O(1) | Best general solution. Efficient and avoids recursion overhead. |
| Recursive Euclidean Algorithm | O(n + log M) | O(log M) | Useful when recursion is preferred or when demonstrating the mathematical definition of GCD. |
Video Solution
Find Greatest Common Divisor of Array | LeetCode 1979 | English • CodeClips with Abhishek Ranjan • 3,974 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find Greatest Common Divisor of Array easy or hard?
Find Greatest Common Divisor of Array Python/Java solution
How to solve Find Greatest Common Divisor of Array in O(n)?
What is the best approach for Find Greatest Common Divisor of Array?
Is Find Greatest Common Divisor of Array asked at Google/Amazon/Meta?
What data structure is used in Find Greatest Common Divisor of Array?
What is the time complexity of Find Greatest Common Divisor of Array?
Ready to solve this problem?
Practice Find Greatest Common Divisor of Array with our built-in code editor and test cases.
Practice on FleetCode