Find Greatest Common Divisor of Array - Video Solutions

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.