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:
- Identify and extract the smallest and the largest numbers from the array.
- 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:
- Utilize the
max()
function to find the largest number in the arraynums
. - Use the
min()
function to find the smallest number in the arraynums
. - 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:
-
Finding the Largest and Smallest Values: The
max()
function iterates through all the elements in thenums
list to return the largest value, while themin()
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. -
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 EvaluatorExample Walkthrough
Let us take an array nums
with the following integers: [24, 36, 12, 18, 48]
.
-
Finding the Largest and Smallest Values:
- Using the
max()
function on our array, we get the largest value48
. This is done by comparing each element and keeping track of the highest one encountered. - Similarly, applying
min()
function, the smallest value12
is found, through a similar process of comparison and keeping track of the lowest one.
- Using the
-
Computing the Greatest Common Divisor:
-
Now that we have the smallest number,
12
, and the largest number,48
, we use thegcd
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 numbers48
(a) and12
(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
becomes0
, the loop ends anda
, which is12
in our case, is the GCD of48
and12
.
-
-
Result: The
gcd
of48
and12
returns12
as the GCD, which is the highest positive integer that divides both48
and12
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.
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
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
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.