Find Greatest Common Divisor of Array solution and explanation
Google
9 more videos on this problem
Find Greatest Common Divisor of Array | LeetCode 1979 | EnglishCodeClips with Abhishek Ranjan · 4:00 · 3K views
1979. Find Greatest Common Divisor of Array (Leetcode Easy)Programming Live with Larry · 2:15 · 1K views
1979. Find Greatest Common Divisor of Array | Leetcode | Arrays | FundamentalsCoding with Tamilarasan · 5:52 · 1K views
1979. Find Greatest Common Divisor of Array | Leetcode Daily - PythonLeetcode Daily · 4:00 · 324 views
Find Greatest Common Divisor of Array | LeetCode 1979 | Java Code | Developer CoderDeveloper Coder · 4:59 · 277 views
Daily Leetcode #2300: Jul 18, 2026 - 1979. Find Greatest Common Divisor of ArrayProgramming Live with Larry · 2:25 · 221 views
1979 Find Greatest Common Divisor of ArrayMath Geeks · 0:51 · 166 views
Find Greatest Common Divisor of Array | LeetCode 1979 - Pythonimpoldev · 2:30 · 153 views
leetcode 1979. Find Greatest Common Divisor of Array - elementary mathCode-Yao · 8:53 · 147 views
LeetCode 1979 Find Greatest Common Divisor of Array in Python | Easy Coding Tutorial for BeginnersJR: Educational Channel · 2:32 · 109 views
The problem
Given an integer array nums, return the greatest common divisor of the smallest number and largest number in nums.
The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.
Example 1:
Input: nums = [2,5,6,9,10] Output: 2 Explanation: The smallest number in nums is 2. The largest number in nums is 10. The greatest common divisor of 2 and 10 is 2.
Example 2:
Input: nums = [7,5,6,8,3] Output: 1 Explanation: The smallest number in nums is 3. The largest number in nums is 8. The greatest common divisor of 3 and 8 is 1.
Example 3:
Input: nums = [3,3] Output: 3 Explanation: The smallest number in nums is 3. The largest number in nums is 3. The greatest common divisor of 3 and 3 is 3.
Constraints:
2 <= nums.length <= 10001 <= nums[i] <= 1000
Approach overview
Problem Overview: Given an integer array nums, return the greatest common divisor (GCD) of the smallest and largest numbers in the array. The key observation is that the GCD of the entire array reduces to the GCD of min(nums) and max(nums).
The task splits into two parts: first scan the array to find the minimum and maximum values, then compute their GCD using the Euclidean algorithm. This problem combines simple array traversal with a classic number theory technique.
Approach 1: Iterative Euclidean Algorithm (O(n + log M) time, O(1) space)
Start by iterating through the array once to compute minVal and maxVal. This takes O(n) time and constant space. After that, compute the GCD using the iterative Euclidean algorithm: repeatedly replace (a, b) with (b, a % b) until b == 0. The remaining value a is the GCD.
The Euclidean algorithm works because the GCD of two numbers does not change when replacing the larger number with its remainder after division. Each iteration reduces the size of the numbers quickly, giving a time complexity of O(log M), where M is the larger number. This approach is efficient, avoids recursion overhead, and works well in languages where iterative loops are preferred.
Approach 2: Recursive Euclidean Algorithm (O(n + log M) time, O(log M) space)
This approach uses the same mathematical idea but expresses the Euclidean algorithm recursively. After computing minVal and maxVal from the array, define a recursive function gcd(a, b). If b == 0, return a. Otherwise return gcd(b, a % b).
Each recursive call reduces the problem size exactly like the iterative version. The recursion depth is at most O(log M), which means the extra stack space is also logarithmic. This version is often considered more elegant and mirrors the mathematical definition of the Euclidean algorithm closely.
Both approaches rely on fundamental concepts from math and number theory. The only array operation needed is a single pass to identify the smallest and largest elements.
Recommended for interviews: The iterative Euclidean algorithm is typically preferred. Interviewers expect you to recognize that only the minimum and maximum values matter, then apply the Euclidean algorithm to compute the GCD efficiently. Mentioning both iterative and recursive forms demonstrates understanding of the underlying number theory, but the iterative version is slightly more practical in production code.
Approach 1: Approach 1: Iterative Euclidean Algorithm
This approach involves first identifying the smallest and largest numbers in the array, then using the iterative Euclidean algorithm to find their GCD.
import math
def findGCD(nums):
min_num = min(nums)
max_num = max(nums)
return math.gcd(min_num, max_num)
nums = [2, 5, 6, 9, 10]
print(findGCD(nums))import java.util.Collections;
import java.util.Arrays;
public class Main {
public static int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
public static int findGCD(int[] nums) {
int min = Arrays.stream(nums).min().getAsInt();
int max = Arrays.stream(nums).max().getAsInt();
return gcd(min, max);
}
public static void main(String[] args) {
int[] nums = {2, 5, 6, 9, 10};
System.out.println(findGCD(nums));
}
}#include <iostream>
#include <algorithm>
int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
int findGCD(std::vector<int>& nums) {
int min = *std::min_element(nums.begin(), nums.end());
int max = *std::max_element(nums.begin(), nums.end());
return gcd(min, max);
}
int main() {
std::vector<int> nums = {2, 5, 6, 9, 10};
std::cout << findGCD(nums) << std::endl;
return 0;
}function gcd(a, b) {
while (b !== 0) {
const t = b;
b = a % b;
a = t;
}
return a;
}
function findGCD(nums) {
const minNum = Math.min(...nums);
const maxNum = Math.max(...nums);
return gcd(minNum, maxNum);
}
const nums = [2, 5, 6, 9, 10];
console.log(findGCD(nums));#include <stdio.h>
int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
int findGCD(int* nums, int numsSize) {
int min = nums[0], max = nums[0];
for (int i = 1; i < numsSize; i++) {
if (nums[i] < min) min = nums[i];
if (nums[i] > max) max = nums[i];
}
return gcd(min, max);
}
int main() {
int nums[] = {2, 5, 6, 9, 10};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", findGCD(nums, size));
return 0;
}using System;
using System.Linq;
public class Program {
public static int GCD(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
public static int FindGCD(int[] nums) {
int min = nums.Min();
int max = nums.Max();
return GCD(min, max);
}
public static void Main() {
int[] nums = {2, 5, 6, 9, 10};
Console.WriteLine(FindGCD(nums));
}
}Leveraging Python's built-in math.gcd function, this approach quickly finds the min and max of the list and computes their GCD.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Approach 2: Recursive Euclidean Algorithm
In this approach, we use the recursive method to implement the Euclidean algorithm for finding the GCD. Identify the minimum and maximum values in the array, then recursively apply the GCD calculation.
import math
def findGCD(nums):
min_num = min(nums)
max_num = max(nums)
return math.gcd(min_num, max_num)
nums = [7, 5, 6, 8, 3]
print(findGCD(nums))import java.util.Arrays;
public class Main {
public static int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
public static int findGCD(int[] nums) {
int min = Arrays.stream(nums).min().getAsInt();
int max = Arrays.stream(nums).max().getAsInt();
return gcd(min, max);
}
public static void main(String[] args) {
int[] nums = {7, 5, 6, 8, 3};
System.out.println(findGCD(nums));
}
}#include <iostream>
#include <algorithm>
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int findGCD(std::vector<int>& nums) {
int min = *std::min_element(nums.begin(), nums.end());
int max = *std::max_element(nums.begin(), nums.end());
return gcd(min, max);
}
int main() {
std::vector<int> nums = {7, 5, 6, 8, 3};
std::cout << findGCD(nums) << std::endl;
return 0;
}function gcd(a, b) {
if (b === 0) return a;
return gcd(b, a % b);
}
function findGCD(nums) {
const minNum = Math.min(...nums);
const maxNum = Math.max(...nums);
return gcd(minNum, maxNum);
}
const nums = [7, 5, 6, 8, 3];
console.log(findGCD(nums));#include <stdio.h>
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int findGCD(int* nums, int numsSize) {
int min = nums[0], max = nums[0];
for (int i = 1; i < numsSize; i++) {
if (nums[i] < min) min = nums[i];
if (nums[i] > max) max = nums[i];
}
return gcd(min, max);
}
int main() {
int nums[] = {7, 5, 6, 8, 3};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", findGCD(nums, size));
return 0;
}using System;
using System.Linq;
public class Program {
public static int GCD(int a, int b) {
if (b == 0)
return a;
return GCD(b, a % b);
}
public static int FindGCD(int[] nums) {
int min = nums.Min();
int max = nums.Max();
return GCD(min, max);
}
public static void Main() {
int[] nums = {7, 5, 6, 8, 3};
Console.WriteLine(FindGCD(nums));
}
}Python's built-in math.gcd function internally uses a recursive method which efficiently computes the GCD. We determine the min and max first to apply it.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Simulation
We can simulate according to the problem description. First, find the maximum and minimum values in the array nums, then find the greatest common divisor of the maximum and minimum values.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
function findGCD(nums: number[]): number {
const min = Math.min(...nums);
const max = Math.max(...nums);
return gcd(min, max);
}
function gcd(a: number, b: number): number {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}func findGCD(nums []int) int {
a, b := slices.Max(nums), slices.Min(nums)
return gcd(a, b)
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}impl Solution {
pub fn find_gcd(nums: Vec<i32>) -> i32 {
let min_val = *nums.iter().min().unwrap();
let max_val = *nums.iter().max().unwrap();
gcd(min_val, max_val)
}
}
fn gcd(mut a: i32, mut b: i32) -> i32 {
while b != 0 {
let temp = b;
b = a % b;
a = temp;
}
a
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Euclidean Algorithm | Time Complexity: O(n) |
| Approach 2: Recursive Euclidean Algorithm | Time Complexity: O(n) |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Euclidean Algorithm | O(n + log M) | O(1) | Best general solution. Efficient and avoids recursion overhead. |
| Recursive Euclidean Algorithm | O(n + log M) | O(log M) | Useful when recursion is preferred or when demonstrating the mathematical definition of GCD. |
Frequently asked questions
Is Find Greatest Common Divisor of Array easy or hard?
LeetCode classifies this problem as Easy with a high acceptance rate around 80%. The difficulty mainly lies in recognizing that the answer only depends on the smallest and largest elements and then applying the Euclidean GCD algorithm correctly.
Find Greatest Common Divisor of Array Python/Java solution
In Python or Java, first compute the minimum and maximum values from the array. Then implement the Euclidean algorithm either iteratively or recursively to compute gcd(minVal, maxVal). Both implementations run in O(n + log M) time and use constant extra space in the iterative version.
How to solve Find Greatest Common Divisor of Array in O(n)?
Traverse the array once to find the smallest and largest elements. After that, apply the Euclidean algorithm to compute gcd(minVal, maxVal). The array traversal costs O(n) and the GCD calculation costs O(log M), giving an overall complexity of O(n + log M).
What is the best approach for Find Greatest Common Divisor of Array?
The optimal approach finds the minimum and maximum elements in the array, then computes their GCD using the Euclidean algorithm. This works because the problem definition only requires the GCD of the smallest and largest numbers. The overall complexity is O(n + log M), where n is the array length and M is the maximum value.
Is Find Greatest Common Divisor of Array asked at Google/Amazon/Meta?
Problems involving the Euclidean algorithm and GCD calculations appear frequently in technical interviews at large companies such as Google, Amazon, and Meta. This specific problem is categorized as easy but tests knowledge of number theory fundamentals and efficient array traversal.
What data structure is used in Find Greatest Common Divisor of Array?
The problem primarily uses an array as the input data structure. The algorithm only requires a linear scan to compute the minimum and maximum values, followed by a mathematical GCD calculation using the Euclidean algorithm.
What is the time complexity of Find Greatest Common Divisor of Array?
The algorithm takes O(n + log M) time. O(n) comes from scanning the array to determine the minimum and maximum values, and O(log M) comes from the Euclidean algorithm used to compute the GCD of those two numbers.