algoadvance

You need to find the Greatest Common Divisor (GCD) of an array of numbers. The GCD of an array is the largest positive integer that divides each of the integers in the array without leaving a remainder.

Example:

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

Input: nums = [7,5,6,8,3]
Output: 1

Input: nums = [3,3]
Output: 3

Constraints:

• 2 <= nums.length <= 1000
• 1 <= nums[i] <= 1000

Clarifying Questions

1. What is the range of values in the array?
   • The array contains integers from 1 to 1000.
2. What is the length of the input array?
   • The length of the array ranges from 2 to 1000.
3. Can the array contain duplicate numbers?
   • Yes, the array can contain duplicate numbers.
4. Are there any special cases to consider, such as all elements being the same?
   • If all elements are the same, the GCD is the number itself.

Strategy

1. Find Extremes: The GCD of an array is influenced heavily by its smallest and largest values, since the greatest common divisor of all elements will be a divisor of any common factors shared by the smallest and largest values.
2. Use Python math Library: Python’s math library contains a convenient gcd function.
3. Pairs Comparison: The GCD of the entire array can be found iteratively using the property gcd(a, b, c) = gcd(gcd(a, b), c).

Code

import math
from functools import reduce

def findGCD(nums):
    return reduce(math.gcd, nums)

# Example usage:
nums1 = [2, 5, 6, 9, 10]
print(findGCD(nums1))  # Output: 1

nums2 = [7, 5, 6, 8, 3]
print(findGCD(nums2))  # Output: 1

nums3 = [3, 3]
print(findGCD(nums3))  # Output: 3

Time Complexity

• Time Complexity: O(n log(min(a, b))) where n is the length of the array. The GCD operation for two numbers a and b takes O(log(min(a, b))), and we are doing this n-1 times.
• Space Complexity: O(1) since we use a constant amount of space irrespective of the input size.

This ensures the solution is efficient and meets the problem’s constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?