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] <= 1000In #1979 Find Greatest Common Divisor of Array, the task is to determine the GCD of all numbers in the array. A key observation from number theory simplifies the problem: the GCD of an entire set of numbers is the same as the GCD of its smallest and largest elements. This works because any common divisor of the full array must also divide both the minimum and maximum values.
Using this idea, you can first scan the array to find the min and max values. Then apply the classic Euclidean Algorithm to compute their GCD efficiently. The Euclidean algorithm repeatedly replaces the larger number with the remainder of division until the remainder becomes zero.
This approach avoids computing pairwise GCDs across the entire array and keeps the implementation simple and efficient. The array traversal takes linear time, while the Euclidean algorithm runs in logarithmic time relative to the numbers involved.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Find min & max + Euclidean GCD | O(n + log M) | O(1) |
| Iterative GCD across array | O(n log M) | O(1) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Find the minimum and maximum in one iteration. Let them be mn and mx.
Try all the numbers in the range [1, mn] and check the largest number which divides both of them.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this type of problem is common in coding interviews because it tests basic number theory concepts and familiarity with the Euclidean algorithm. Variations of GCD-based problems frequently appear in technical interview rounds.
Only a simple array traversal is required for this problem. No advanced data structures are necessary since you just track the minimum and maximum values and apply the Euclidean GCD algorithm.
The optimal approach is to find the minimum and maximum elements in the array and compute their GCD using the Euclidean algorithm. A mathematical property guarantees that the GCD of the entire array equals the GCD of its smallest and largest values.
Any divisor that divides every number in the array must also divide both the smallest and largest elements. Because of this property, calculating the GCD of these two boundary values yields the same result as computing it across the entire array.