1979. Find Greatest Common Divisor of Array

Problem Description

The LeetCode problem at hand requires finding the greatest common divisor (GCD) of the smallest and largest numbers in a given array of integers, nums. The GCD is the highest positive integer that can divide both numbers without leaving a remainder.

To break down the steps we need to follow:

1. Identify and extract the smallest and the largest numbers from the array.
2. Calculate the GCD of these two numbers.

Intuition

To solve this problem efficiently, our solution employs the built-in gcd function from Python's math library and two functions max() and min().

Here's the step-by-step thought process:

1. Utilize the max() function to find the largest number in the array nums.
2. Use the min() function to find the smallest number in the array nums.
3. Apply the gcd function, which computes the greatest common divisor of two numbers.

By using these built-in functions, we abstract away the complexity of writing our own algorithms for finding maximum and minimum values and computing the GCD. This allows our solution to be concise and maintain good performance.

Learn more about Math patterns.

Solution Approach

In this problem, the implementation of the solution is fairly straightforward due to Python's powerful built-in functions. Here is how the algorithm and data structures involved work:

1. Finding the Largest and Smallest Values: The max() function iterates through all the elements in the nums list to return the largest value, while the min() function does the same to return the smallest value. Under the hood, each of these functions performs a linear scan through the list, which is a simple but effective algorithm.

2. Computing the Greatest Common Divisor: The gcd function implemented in Python's math library uses the Euclidean algorithm. This age-old algorithm is an efficient way to compute the greatest common divisor of two numbers a and b (where a ≥ b). The process is as follows:

   1while b ≠ 0:
   2    temp = b
   3    b = a % b  # '%' is the modulo operator
   4    a = temp
   5# At the end of the loop, 'a' holds the GCD of the original a and b

In terms of data structures, we only deal with the array structure (Python list) containing the input numbers. There is no need for additional data structures as Python's built-in functions handle the necessary operations internally.

The reference solution code effectively leverages these functions, resulting in a clean and efficient solution:

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

Here the max(nums) call finds the largest number in nums, min(nums) finds the smallest, and gcd() calculates their greatest common divisor. The key advantage of this approach is its simplicity and the fact that it relies on well-optimized library functions that likely outperform any custom implementation for the same task.

Example Walkthrough

Let us take an array nums with the following integers: [24, 36, 12, 18, 48].

1. Finding the Largest and Smallest Values:

   • Using the max() function on our array, we get the largest value 48. This is done by comparing each element and keeping track of the highest one encountered.
   • Similarly, applying min() function, the smallest value 12 is found, through a similar process of comparison and keeping track of the lowest one.

2. Computing the Greatest Common Divisor:

   • Now that we have the smallest number, 12, and the largest number, 48, we use the gcd function from Python's math library to compute the greatest common divisor of these two numbers.

   • The gcd function performs the Euclidean algorithm behind the scenes. For our numbers 48 (a) and 12 (b), the algorithm works as follows:

     1while b ≠ 0:
     2    temp = b
     3    b = a % b  # b becomes 48 % 12, which is 0
     4    a = temp   # a becomes 12

     As soon as b becomes 0, the loop ends and a, which is 12 in our case, is the GCD of 48 and 12.

3. Result: The gcd of 48 and 12 returns 12 as the GCD, which is the highest positive integer that divides both 48 and 12 without any remainder.

Following these steps with max(nums), min(nums), and gcd(), we find that the GCD of the smallest and largest numbers in the given array [24, 36, 12, 18, 48] is 12.

Solution Implementation

Time and Space Complexity

The time complexity of the provided code is O(N) where N is the number of elements in the nums list. This is because the max(nums) and min(nums) functions each require a full pass through the list to find the respective maximum and minimum values, and each pass is O(N). Both operations are sequential and do not depend on each other's results, therefore the time complexity does not compound.

The space complexity of the code is O(1) since it uses a fixed amount of extra space. The gcd calculation and the retrieval of the max and min values are done in-place without allocating additional space proportional to the input size.

Learn more about how to find time and space complexity quickly using problem constraints.