1979. Find Greatest Common Divisor of Array

EasyArrayMathNumber Theory
Leetcode Link

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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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

1from typing import List
2from math import gcd
3
4class Solution:
5    def findGCD(self, nums: List[int]) -> int:
6        """
7        Computes the greatest common divisor (GCD) of the maximum and
8        minimum numbers in the given list.
9
10        :param nums: List of integers
11        :return: The GCD of the max and min values in the list
12        """
13        # Find the maximum value in the list
14        max_num = max(nums)
15        # Find the minimum value in the list
16        min_num = min(nums)
17      
18        # Compute the GCD of the max and min values
19        return gcd(max_num, min_num)
20
1class Solution {
2  
3    // Method to find the Greatest Common Divisor (GCD) of the largest and smallest numbers in the array.
4    public int findGCD(int[] nums) {
5        // Initialize maxNum to the smallest possible integer value and minNum to the largest possible integer value
6        int maxNum = Integer.MIN_VALUE;
7        int minNum = Integer.MAX_VALUE;
8      
9        // Iterate through all numbers in the array
10        for (int num : nums) {
11            // Update the maxNum with the maximum value found so far
12            maxNum = Math.max(maxNum, num);
13            // Update the minNum with the minimum value found so far
14            minNum = Math.min(minNum, num);
15        }
16      
17        // Return the GCD of the largest and smallest numbers found in the array
18        return gcd(maxNum, minNum);
19    }
20
21    // Helper method to calculate GCD of two numbers using the Euclidean algorithm
22    private int gcd(int a, int b) {
23        // If b is 0, we have found the GCD and return a
24        if (b == 0) {
25            return a;
26        }
27        // Recursively call the gcd method with b and the remainder of a divided by b
28        return gcd(b, a % b);
29    }
30}
31
1#include <vector>
2#include <algorithm> // Include necessary headers
3
4class Solution {
5public:
6    // Function to find the greatest common divisor (GCD) of the max and min
7    // element in a vector of integers.
8    int findGCD(std::vector<int>& nums) {
9        // Find the maximum element in the vector
10        int maxElement = *std::max_element(nums.begin(), nums.end());
11        // Find the minimum element in the vector
12        int minElement = *std::min_element(nums.begin(), nums.end());
13      
14        // Return the GCD of the max and min elements
15        return gcd(maxElement, minElement);
16    }
17
18private:
19    // Helper function to compute the GCD of two numbers using Euclid's algorithm
20    int gcd(int a, int b) {
21        // Continue until no remainder is left
22        while (b != 0) {
23            int temp = b;
24            b = a % b;  // Replace b with the remainder of a divided by b
25            a = temp;   // Replace a with b
26        }
27        return a; // When b is 0, a contains the GCD
28    }
29};
30
1/**
2 * Finds the Greatest Common Divisor (GCD) of two numbers, 
3 * utilizing the Euclidean algorithm.
4 * @param a The first number.
5 * @param b The second number.
6 * @return The GCD of a and b.
7 */
8function gcd(a: number, b: number): number {
9    // Base case: if b is 0, a is the GCD
10    if (b === 0) {
11        return a;
12    }
13    // Recursive case: call gcd with b and the remainder of a divided by b
14    return gcd(b, a % b);
15}
16
17/**
18 * Finds the GCD of the smallest and largest numbers in the provided array.
19 * @param nums The array of non-negative integers.
20 * @return The GCD of the smallest and largest integers in nums.
21 */
22function findGCD(nums: number[]): number {
23    // Initialize variables to store the smallest and largest numbers
24    // Start with opposite extremes for comparison
25    // 'maxValue' will hold the largest number in the array
26    // 'minValue' will hold the smallest number in the array
27    let maxValue: number = 1;
28    let minValue: number = 1000;
29
30    // Iterate through all numbers in the array to find the smallest
31    // and largest numbers
32    for (const num of nums) {
33        // Update the largest number (maxValue) found so far
34        maxValue = Math.max(maxValue, num);
35        // Update the smallest number (minValue) found so far
36        minValue = Math.min(minValue, num);
37    }
38
39    // Return the GCD of the largest and smallest number in the array
40    return gcd(maxValue, minValue);
41}
42

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.