Greatest Common Divisor Traversal
The key idea
Two values can be traversed between when they share a common prime factor. So treat each index as a node and connect indices that share a prime. The answer is
true exactly when all indices land in one connected component, which Union-Find decides efficiently.Problem
You are given a 0-indexed integer array nums, and you can traverse between index i and index j (with i != j) if and only if gcd(nums[i], nums[j]) > 1, where gcd is the greatest common divisor.
Your task is to determine whether for every pair of indices i and j (where 0 <= i < j <= n - 1) there exists a sequence of traversals that can take you from i to j.
Return true if it is possible to traverse between all such pairs of indices, or false otherwise. Note that a single element can never reach a different element when its value is 1, since 1 shares no prime factor with anything.
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^5
Examples
Input: nums = [2,3,6]
Output: true
Input: nums = [3,9,5]
Output: false
Input: nums = [4,3,12,8]
Output: true
Complexity
Time: O(n + M log log M) Space: O(n + M)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization