How do you solve Find Greatest Common Divisor of Array on LeetCode?

Find Greatest Common Divisor of Array (LeetCode #1979) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Finding the minimum and maximum in one pass can save time.

What is the brute force solution for Find Greatest Common Divisor of Array?

The brute force approach for Find Greatest Common Divisor of Array is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking every number from 1 to the smallest number in the array to see if it divides both the smallest and largest numbers. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Find Greatest Common Divisor of Array?

Find Greatest Common Divisor of Array uses the following concepts: Array, Math, Number Theory. The recommended patterns to study are: Math, Array.

What are the interview tips for Find Greatest Common Divisor of Array?

Always clarify the problem statement and constraints before jumping to code. Think about edge cases and how your solution handles them. Discuss your thought process and approach with the interviewer; they value understanding over just getting the right answer.

What are common mistakes when solving Find Greatest Common Divisor of Array?

Not considering edge cases, such as when all numbers are the same. Overcomplicating the problem by trying to find GCD for all pairs instead of just min and max.

#1979

Find Greatest Common Divisor of Array

Easy

ArrayMathNumber TheoryMathArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution leverages the mathematical property of the greatest common divisor (GCD) and uses the built-in GCD function to compute the result efficiently.

⚙️

Algorithm

3 steps

1Step 1: Find the minimum (mn) and maximum (mx) values in the array in one pass.
2Step 2: Use the built-in GCD function to compute the GCD of mn and mx.
3Step 3: Return the result.

solution.py7 lines

1# Full working Python code
2import math
3
4def findGCD(nums):
5    mn = min(nums)
6    mx = max(nums)
7    return math.gcd(mn, mx)

ℹ

Complexity note: The time complexity is O(n) because we find the min and max in a single pass through the array. The GCD calculation is O(log(min, max)) which is efficient. The space complexity is O(1) since we only use a few variables.

1Finding the minimum and maximum in one pass can save time.
2Using built-in functions for GCD can optimize performance significantly.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.