Greatest Common Divisor Traversal
Problem Description
You are given a 0-indexed integer array nums, and you are allowed to traverse between its indices. You can traverse between index i and index j (i != j) if and only if gcd(nums[i], nums[j]) > 1, where gcd is the greatest common divisor.
Your task is to determine if for every pair of indices i and j in nums, there exists a sequence of traversals that can take us from i to j.
Return true if all pairs of indices are traversable, or false otherwise.
Examples
Example 1:Input: nums = [2,3,6] Output: true Explanation:
- We can go from index 0 to 2 because gcd(2, 6) = 2 > 1.
- We can go from index 2 to 1 because gcd(6, 3) = 3 > 1. So all indices are reachable from each other.
Input: nums = [3,9,5] Output: false
Input: nums = [4,3,12,8] Output: true
Constraints
1 ≤ nums.length ≤ 10⁵1 ≤ nums[i] ≤ 10⁵
Union-Find on Prime Factors
We want to check if the graph of indices is fully connected. An edge exists between indices i and j if nums[i] and nums[j] share a prime factor.
Checking every pair of indices costs O(N²), which will TLE when N = 10⁵.
Instead, we can union indices via their prime factors:
- For each number
nums[i], find its prime factors using trial division up to√val. - Map each prime factor to the first index
iwhere it appeared. - If a prime factor
pis seen again at indexj, unionjwith the first index that hadp. - At the end, check if all indices have been merged into a single connected component.
Edge Case: if nums.length == 1, return true (traversal is vacuously possible). If any value is 1 (which has no prime factors) and nums.length > 1, it can never connect to any other index, so return false.
Solution: Union-Find on Primes
import java.util.*;
class Solution {
class UnionFind {
int[] parent;
int count;
UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
count = n;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void union(int x, int y) {
int px = find(x), py = find(y);
if (px != py) {
parent[px] = py;
count--;
}
}
}
public boolean canTraverseAllPairs(int[] nums) {
int n = nums.length;
if (n == 1) return true;
UnionFind uf = new UnionFind(n);
// primeToFirstIndex: maps prime factor -> index of first number having it
Map<Integer, Integer> primeToFirstIndex = new HashMap<>();
for (int i = 0; i < n; i++) {
int val = nums[i];
if (val == 1) return false; // 1 cannot share any factor > 1
int temp = val;
for (int d = 2; d * d <= temp; d++) {
if (temp % d == 0) {
if (primeToFirstIndex.containsKey(d)) {
uf.union(i, primeToFirstIndex.get(d));
} else {
primeToFirstIndex.put(d, i);
}
while (temp % d == 0) temp /= d;
}
}
if (temp > 1) {
if (primeToFirstIndex.containsKey(temp)) {
uf.union(i, primeToFirstIndex.get(temp));
} else {
primeToFirstIndex.put(temp, i);
}
}
}
return uf.count == 1;
}
}class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.count = n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = py
self.count -= 1
class Solution:
def canTraverseAllPairs(self, nums: list[int]) -> bool:
n = len(nums)
if n == 1:
return True
uf = UnionFind(n)
prime_to_first_idx = {}
for i, val in enumerate(nums):
if val == 1:
return False
temp = val
d = 2
while d * d <= temp:
if temp % d == 0:
if d in prime_to_first_idx:
uf.union(i, prime_to_first_idx[d])
else:
prime_to_first_idx[d] = i
while temp % d == 0:
temp //= d
d += 1
if temp > 1:
if temp in prime_to_first_idx:
uf.union(i, prime_to_first_idx[temp])
else:
prime_to_first_idx[temp] = i
return uf.count == 1#include <vector>
#include <unordered_map>
#include <numeric>
class Solution {
struct UnionFind {
std::vector<int> parent;
int count;
UnionFind(int n) : count(n) {
parent.resize(n);
std::iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void unite(int x, int y) {
int px = find(x), py = find(y);
if (px != py) {
parent[px] = py;
count--;
}
}
};
public:
bool canTraverseAllPairs(std::vector<int>& nums) {
int n = nums.size();
if (n == 1) return true;
UnionFind uf(n);
std::unordered_map<int, int> primeToFirstIndex;
for (int i = 0; i < n; i++) {
int val = nums[i];
if (val == 1) return false;
int temp = val;
for (int d = 2; d * d <= temp; d++) {
if (temp % d == 0) {
if (primeToFirstIndex.count(d)) {
uf.unite(i, primeToFirstIndex[d]);
} else {
primeToFirstIndex[d] = i;
}
while (temp % d == 0) temp /= d;
}
}
if (temp > 1) {
if (primeToFirstIndex.count(temp)) {
uf.unite(i, primeToFirstIndex[temp]);
} else {
primeToFirstIndex[temp] = i;
}
}
}
return uf.count == 1;
}
};Complexity Analysis:
- Time Complexity: O(N * √V) where N is the length of
numsand V is the maximum valuenums[i](at most 10⁵). Finding prime factors of a value V takes O(√V) time. Union-find operations take O(alpha(N)) which is constant. - Space Complexity: O(N + P) where P is the number of unique prime factors seen (at most 10000 primes under 10⁵).