Find Greatest Common Divisor Of Array - Leetcode Solution

Problem Statement:

Given an array of integers, find the greatest common divisor (GCD) of the array elements.

Example 1: Input: nums = [2,4,6,8,10] Output: 2 Explanation: The greatest common divisor of all numbers is 2.

Example 2: Input: nums = [3,6,9,12] Output: 3 Explanation: The greatest common divisor of all numbers is 3.

Solution:

To find the greatest common divisor of an array of integers, we can use the Euclidean algorithm. Here's how it works:

• Find the GCD of the first two numbers in the array
• Use the GCD found in step 1 and find the GCD with the next number in the array
• Repeat step 2 until the end of the array is reached
• The final GCD found in step 3 is the GCD of the array

Let's implement the algorithm in code:

class Solution: def gcd(self, a, b): # base case if b == 0: return a return self.gcd(b, a % b)

def findGCD(self, nums: List[int]) -> int:
    # find GCD of first two numbers
    gcd_num = self.gcd(nums[0], nums[1])
    
    # find GCD with each subsequent number
    for i in range(2, len(nums)):
        gcd_num = self.gcd(gcd_num, nums[i])
        
    return gcd_num

In the code above, we define the gcd method that implements the Euclidean algorithm recursively. We then use this method to find the GCD of the array by finding the GCD of the first two numbers and then finding the GCD with each subsequent number using a for loop.

Time Complexity: The time complexity of the above solution is O(nlogn) because the Euclidean algorithm has a time complexity of O(logn) and we perform this operation n-1 times for an array of n integers.

Space Complexity: The space complexity of the above solution is O(1) because we are not using any extra space for computation.

1