#1979

Easy

LeetCode Problem Workspace

Find Greatest Common Divisor of Array

Find the greatest common divisor of the smallest and largest numbers in an integer array.

Problem Statement

You are given an integer array nums. The task is to find the greatest common divisor (GCD) of the smallest and largest numbers in the array.

The GCD of two numbers is the largest positive integer that divides both numbers without leaving a remainder. Your solution should handle arrays with a length between 2 and 1000 and values in the range from 1 to 1000.

Examples

Example 1

Input: nums = [2,5,6,9,10]

Output: 2

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

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

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 Approach

Find Min and Max

First, iterate through the array to find the minimum and maximum values in a single pass. This reduces the time complexity to O(n) for finding these values.

Calculate GCD

Once you have the minimum and maximum values, use the Euclidean algorithm or another method to calculate their greatest common divisor. This step takes O(log(min, max)) time.

Optimize for Large Arrays

For larger arrays, consider that finding min and max in one pass minimizes the complexity. Always ensure the GCD calculation is efficient, especially for large values.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution is O(n) for finding the minimum and maximum values in the array. The GCD computation has a time complexity of O(log(min, max)), where min and max are the smallest and largest numbers in the array.

What Interviewers Usually Probe

Look for an efficient approach to find the min and max values in one iteration.
Ensure that the candidate uses an efficient method like the Euclidean algorithm for GCD.
Watch for edge cases such as arrays with identical elements, where GCD is the element itself.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding that the problem only asks for the GCD of the smallest and largest numbers, not all pairs.
Not handling arrays with identical elements correctly, where the GCD should be the element itself.
Using an inefficient method to find the minimum and maximum values, causing unnecessary time complexity.

Follow-up variants

Find the GCD of the largest two elements instead of min and max.
Calculate the GCD for multiple pairs within the array and return the smallest GCD.
Allow larger arrays, potentially introducing more optimization techniques for finding the min and max.

FAQ

What is the main approach for solving the 'Find Greatest Common Divisor of Array' problem?

The main approach is to find the minimum and maximum values in the array in a single iteration, then calculate their greatest common divisor using an efficient method like the Euclidean algorithm.

How does the Euclidean algorithm work for GCD?

The Euclidean algorithm works by repeatedly subtracting the smaller number from the larger one until one number becomes zero. The non-zero number is the GCD.

Can the problem be solved with a more efficient approach for large arrays?

Yes, by finding the min and max values in one pass and using an efficient GCD algorithm, the solution can handle large arrays efficiently.

What is the time complexity of the solution?

The time complexity is O(n) for finding the min and max values, and O(log(min, max)) for computing the GCD.

Are there any edge cases to consider in the 'Find Greatest Common Divisor of Array' problem?

Yes, edge cases include arrays with identical elements, where the GCD is the element itself, and arrays with very large or small numbers.

terminal

Solution

Solution 1: Simulation

We can simulate according to the problem description. First, find the maximum and minimum values in the array $\textit{nums}$, then find the greatest common divisor of the maximum and minimum values.

1

2

3

class Solution:
    def findGCD(self, nums: List[int]) -> int:
        return gcd(max(nums), min(nums))

Continue Practicing

#1994 the number of good subsets #1998 gcd sort of an array #2001 number of pairs of interchangeable rectangles