Find Greatest Common Divisor of Array
Easy
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.
For example:
nums = [2, 5, 6, 9, 10]should return2. The smallest number is 2 and the largest is 10. GCD(2, 10) = 2.nums = [7, 5, 6, 8, 3]should return1. The smallest number is 3 and the largest is 8. GCD(3, 8) = 1.nums = [3, 3]should return3. The smallest number is 3 and the largest is 3. GCD(3, 3) = 3.
Consider edge cases such as:
- What happens if the input array is empty?
- What happens if all the numbers in the array are the same?
How can you optimize the solution for large arrays? Write an efficient algorithm to find the GCD. What is the time and space complexity of your approach?
Solution
Naive Approach: Brute Force
A straightforward approach is to first find the smallest and largest numbers in the array. Then, iterate from 1 up to the smaller of the two numbers, checking if each number divides both the smallest and largest numbers evenly. The largest such number is the GCD.
Code (Python)
def gcd_brute_force(nums):
smallest = min(nums)
largest = max(nums)
gcd = 1
for i in range(1, smallest + 1):
if smallest % i == 0 and largest % i == 0:
gcd = i
return gcd
Time Complexity
O(n + min(smallest, largest)), where n is the length of the array nums.
Space Complexity
O(1)
Optimal Approach: Euclidean Algorithm
The Euclidean algorithm is a more efficient way to find the GCD of two numbers. The basic idea is to repeatedly apply the division algorithm until the remainder is 0. The GCD is the last non-zero remainder.
Code (Python)
def gcd_euclidean(a, b):
while(b):
a, b = b, a % b
return a
def find_gcd_of_min_max(nums):
smallest = min(nums)
largest = max(nums)
return gcd_euclidean(smallest, largest)
Explanation
- Find Minimum and Maximum: First, determine the smallest and largest numbers in the array
nums. This step takes O(n) time. - Euclidean Algorithm: Apply the Euclidean algorithm to find the GCD of the smallest and largest numbers. The algorithm repeatedly divides the larger number by the smaller number and takes the remainder until the remainder is 0. The last non-zero remainder is the GCD.
Edge Cases
- If the array is empty, it might throw an error while finding min/max. Handle that case separately.
- If all numbers in the array are the same, the GCD will be the number itself.
Time Complexity
The time complexity of the Euclidean algorithm is O(log(min(a, b))), where a and b are the two numbers for which we are finding the GCD. Finding the minimum and maximum takes O(n) time. Therefore, the overall time complexity is O(n + log(min(smallest, largest))).
Space Complexity
The space complexity is O(1) because the algorithm uses a constant amount of extra space, regardless of the input size.
