Greatest Common Divisor Traversal
Problem
You may traverse between indices i and j (i ≠ j) exactly when gcd(nums[i], nums[j]) > 1. Return true if for every pair of indices there is a sequence of traversals connecting them — that is, if all indices form a single connected component.
nums = [2, 3, 6]truedef canTraverseAllPairs(nums):
n = len(nums)
if n == 1:
return True # a single index is trivially connected
if any(v == 1 for v in nums):
return False # gcd(1, x) == 1, so a 1 can never link
parent = list(range(n)) # Union-Find over the n indices
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path compression
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
owner = {} # prime -> first index that carried it
for i, v in enumerate(nums):
x = v
f = 2
while f * f <= x: # factor out every prime up to sqrt(x)
if x % f == 0:
while x % f == 0:
x //= f
if f in owner:
union(i, owner[f])
else:
owner[f] = i
f += 1
if x > 1: # leftover prime factor
if x in owner:
union(i, owner[x])
else:
owner[x] = i
root = find(0) # all indices must share one root
return all(find(i) == root for i in range(n))function canTraverseAllPairs(nums) {
const n = nums.length;
if (n === 1) return true; // a single index is trivially connected
if (nums.some(v => v === 1)) return false; // a 1 can never link
const parent = Array.from({ length: n }, (_, i) => i);
function find(x) {
while (parent[x] !== x) {
parent[x] = parent[parent[x]]; // path compression
x = parent[x];
}
return x;
}
function union(a, b) {
const ra = find(a), rb = find(b);
if (ra !== rb) parent[ra] = rb;
}
const owner = new Map(); // prime -> first index that carried it
for (let i = 0; i < n; i++) {
let x = nums[i];
for (let f = 2; f * f <= x; f++) { // factor out every prime up to sqrt(x)
if (x % f === 0) {
while (x % f === 0) x = Math.floor(x / f);
if (owner.has(f)) union(i, owner.get(f));
else owner.set(f, i);
}
}
if (x > 1) { // leftover prime factor
if (owner.has(x)) union(i, owner.get(x));
else owner.set(x, i);
}
}
const root = find(0); // all indices must share one root
for (let i = 0; i < n; i++) if (find(i) !== root) return false;
return true;
}boolean canTraverseAllPairs(int[] nums) {
int n = nums.length;
if (n == 1) return true; // a single index is trivially connected
for (int v : nums) if (v == 1) return false; // a 1 can never link
int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
Map<Integer, Integer> owner = new HashMap<>(); // prime -> first index
for (int i = 0; i < n; i++) {
int x = nums[i];
for (int f = 2; f * f <= x; f++) { // factor out primes up to sqrt(x)
if (x % f == 0) {
while (x % f == 0) x /= f;
if (owner.containsKey(f)) union(parent, i, owner.get(f));
else owner.put(f, i);
}
}
if (x > 1) { // leftover prime factor
if (owner.containsKey(x)) union(parent, i, owner.get(x));
else owner.put(x, i);
}
}
int root = find(parent, 0); // all indices share one root
for (int i = 0; i < n; i++) if (find(parent, i) != root) return false;
return true;
}
int find(int[] parent, int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}
void union(int[] parent, int a, int b) {
int ra = find(parent, a), rb = find(parent, b);
if (ra != rb) parent[ra] = rb;
}vector<int> par;
int find(int x) {
while (par[x] != x) { par[x] = par[par[x]]; x = par[x]; }
return x;
}
void uni(int a, int b) {
int ra = find(a), rb = find(b);
if (ra != rb) par[ra] = rb;
}
bool canTraverseAllPairs(vector<int>& nums) {
int n = nums.size();
if (n == 1) return true; // single index is trivially connected
for (int v : nums) if (v == 1) return false; // a 1 can never link
par.resize(n);
for (int i = 0; i < n; i++) par[i] = i;
unordered_map<int, int> owner; // prime -> first index that carried it
for (int i = 0; i < n; i++) {
int x = nums[i];
for (int f = 2; f * f <= x; f++) { // factor out primes up to sqrt(x)
if (x % f == 0) {
while (x % f == 0) x /= f;
if (owner.count(f)) uni(i, owner[f]);
else owner[f] = i;
}
}
if (x > 1) { // leftover prime factor
if (owner.count(x)) uni(i, owner[x]);
else owner[x] = i;
}
}
int root = find(0); // all indices share one root
for (int i = 0; i < n; i++) if (find(i) != root) return false;
return true;
}Explanation
Two indices can be traversed directly when their values share a factor greater than 1 — equivalently, when they share a prime factor. The question "can we reach every index from every other" is exactly asking whether the indices form a single connected component under this relation.
Building an edge for every qualifying pair would be quadratic. Instead we connect indices through their primes: keep a map owner from each prime to the first index that contained it. When a later index contains the same prime, we union it with that owner. Linking each index to one representative per prime is enough — transitivity through the owner stitches all sharers of that prime into one group.
The Union-Find (disjoint-set) structure makes union and find almost constant time with path compression. To factor a value we trial-divide by every f with f*f ≤ x, stripping each prime fully, and treat any remainder above 1 as one last prime.
Two quick exits: if there is a single element it is trivially connected, and if any value equals 1 it shares no prime with anything, so the answer is immediately false.
Finally we pick the root of index 0 and confirm every index resolves to that same root. If so, all pairs are mutually reachable and we return true.
Example: nums = [2, 3, 6]. Index 2 (value 6) owns primes 2 and 3 already claimed by indices 0 and 1, so it unions with both — one component, answer true. For [3, 9, 5] the value 5 shares no prime with 3 or 9, leaving two components and answer false.