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] <= 1000This approach involves first identifying the smallest and largest numbers in the array, then using the iterative Euclidean algorithm to find their GCD.
The code follows the Euclidean algorithm to compute the GCD of two numbers by iteratively applying the formula a = b and b = a % b until b becomes 0. The minimum and maximum values are derived from the array to apply this algorithm.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log(min(a, b)))
Space Complexity: O(1)
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.
This C code takes a recursive approach to calculate the GCD using Euclidean method, recursively solving for gcd(b, a % b) until b is zero.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log(min(a, b)))
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Euclidean Algorithm | Time Complexity: O(log(min(a, b))) |
| Approach 2: Recursive Euclidean Algorithm | Time Complexity: O(log(min(a, b))) |
Greatest Common Divisor of Strings - Leetcode 1071 - Python • NeetCodeIO • 76,336 views views
Watch 9 more video solutions →Practice Find Greatest Common Divisor of Array with our built-in code editor and test cases.
Practice on FleetCode