Find Greatest Common Divisor of Array

Problem Description

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.

Key Insights

• The problem requires us to find the smallest and largest numbers in the array.
• The greatest common divisor (GCD) can be calculated using the Euclidean algorithm.
• The GCD of a number with itself is the number itself.
• The constraints ensure that the input array will always have at least two elements.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input array. This accounts for finding the min and max values in a single pass. Space Complexity: O(1), as we are using a constant amount of extra space.

Solution

To solve this problem, we will:

1. Iterate through the nums array to find the smallest and largest numbers.
2. Use the Euclidean algorithm to compute the GCD of these two numbers. The algorithm repeatedly replaces the larger number by the remainder of the division of the larger number by the smaller number until one of the numbers becomes zero.

The primary data structures used here are simple variables to hold the minimum, maximum, and the result of the GCD operation.

Code Solutions