242. Edge GCD
A warehouse stores crates in square-tile grids, and each shelf is labelled with the number of tiles it holds. Given an array nums of positive integers, find the smallest value and the largest value in the array and return the greatest common divisor of those two numbers.
The greatest common divisor of two positive integers is the largest integer that divides both without a remainder. If the array has a single element, that element is both the smallest and the largest, so the answer is the element itself. For instance, with nums = [40, 9, 25] the smallest is 9 and the largest is 40, and since they share no factor above 1, the answer is 1.
Scan the array once and use the Euclidean algorithm, for a total of O(n + log(max)) time and O(1) extra space.
Example 1
- Input:
- nums = [84,15,36,210,126]
- Output:
- 15
- Explanation:
The smallest value is 15 and the largest is 210, and gcd(15, 210) = 15.
Example 2
- Input:
- nums = [17,51,34]
- Output:
- 17
- Explanation:
The smallest is 17 and the largest is 51, which is exactly three times 17, so the gcd is 17.
Constraints
1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 231 - 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n + log max)
- Space
- O(1)