1425. Shared Divisor Count
A tile factory cuts boards of several lengths, and a customer wants square pieces of one whole-number side that fit every board exactly with nothing left over. Given the array nums of board lengths, return how many positive integers divide every element of nums, that is, how many different side lengths are possible. Compute g, the greatest common divisor of all values, then count the divisors of g by trial division up to its square root, counting a square root only once. The expected running time is O(n log V + sqrt(V)) with O(1) extra space, where V is the largest value.
Example 1
- Input:
- nums = [12,18]
- Output:
- 4
- Explanation:
The gcd is 6, which has the divisors 1, 2, 3 and 6, so the answer is 4.
Example 2
- Input:
- nums = [7,13]
- Output:
- 1
- Explanation:
The gcd is 1, whose only divisor is 1, so the answer is 1.
Constraints
1 ≤ n = nums.length ≤ 1000
1 ≤ nums[i] ≤ 109
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 V + sqrt(V))
- Space
- O(1)