Greatest Common Divisor Traversal
Description
You are given a 0-indexed integer array nums. You can traverse between index i and index j (where i ≠ j) if and only if gcd(nums[i], nums[j]) > 1 — that is, the values at those positions share at least one common factor greater than 1.
Determine whether for every pair of indices i and j (where i < j), there exists some sequence of valid traversals that connects them. The path does not need to be direct — you may hop through intermediate indices as long as each consecutive hop satisfies the GCD condition.
Return true if all pairs of indices are reachable from each other through some chain of valid traversals, or false otherwise.
Examples
Example 1
Input: nums = [2, 3, 6]
Output: true
Explanation: We can traverse between all pairs:
- Index 0 → Index 2: gcd(2, 6) = 2 > 1 ✓ (direct)
- Index 2 → Index 1: gcd(6, 3) = 3 > 1 ✓ (direct)
- Index 0 → Index 1: go via index 2. Path: 0 → 2 → 1.
The number 6 at index 2 acts as a bridge because it shares factor 2 with nums[0] and factor 3 with nums[1].
Example 2
Input: nums = [3, 9, 5]
Output: false
Explanation: Index 0 (value 3) and index 1 (value 9) are connected: gcd(3, 9) = 3 > 1. However, index 2 (value 5) shares no common factor with either 3 or 9. Since 5 is prime and distinct from 3, there is no path from index 2 to any other index.
Example 3
Input: nums = [4, 3, 12, 8]
Output: true
Explanation: All indices are reachable:
- gcd(4, 12) = 4 > 1 → indices 0 and 2 connected
- gcd(3, 12) = 3 > 1 → indices 1 and 2 connected
- gcd(4, 8) = 4 > 1 → indices 0 and 3 connected
Index 2 (value 12) is the central bridge connecting everything because 12 = 2² × 3 shares factors with all other elements.
Constraints
- 1 ≤ nums.length ≤ 10^5
- 1 ≤ nums[i] ≤ 10^5
Editorial
Brute Force - Check All Pairs with GCD
Intuition
The most direct way to solve this is to model it as a graph connectivity problem. Think of each index as a node. Two nodes are directly connected by an edge if the GCD of their values is greater than 1. The question then becomes: is this graph fully connected? That is, can we reach every node from every other node?
To build this graph, we check every pair of indices (i, j) and compute gcd(nums[i], nums[j]). If the GCD is greater than 1, we add an edge between them. After building the graph, we run a BFS or DFS from any starting node and check if it visits all nodes. If yes, the graph is connected and we return true.
Step-by-Step Explanation
Let's trace through nums = [2, 3, 6].
Step 1: Check all pairs for GCD > 1:
- Pair (0, 1): gcd(2, 3) = 1. No edge.
- Pair (0, 2): gcd(2, 6) = 2. Add edge 0-2.
- Pair (1, 2): gcd(3, 6) = 3. Add edge 1-2.
Step 2: Adjacency list built: {0: [2], 1: [2], 2: [0, 1]}.
Step 3: Run BFS from node 0. Queue starts: [0]. Mark 0 visited.
Step 4: Dequeue 0. Neighbors: [2]. Enqueue 2, mark visited. Visited = {0, 2}.
Step 5: Dequeue 2. Neighbors: [0, 1]. Node 0 already visited. Enqueue 1, mark visited. Visited = {0, 2, 1}.
Step 6: Dequeue 1. Neighbors: [2]. Node 2 already visited. Queue empty.
Step 7: Visited set has 3 elements = n. All nodes reached → return true.
Now consider nums = [3, 9, 5]:
Step 8: Pairs: gcd(3,9)=3 → edge 0-1. gcd(3,5)=1 → no edge. gcd(9,5)=1 → no edge.
Step 9: BFS from 0: visits {0, 1}. Size 2 ≠ 3. Node 2 (value 5) is isolated → return false.
Brute Force — Building GCD Graph and Checking Connectivity — Watch how we check all pairs for GCD > 1 to build edges, then use BFS to verify full connectivity.
Algorithm
- Build an adjacency list graph with n nodes (one per index).
- For every pair of indices (i, j) where i < j:
- Compute gcd(nums[i], nums[j]).
- If GCD > 1, add an edge between i and j.
- Run BFS or DFS starting from node 0.
- If all n nodes are visited, return true. Otherwise, return false.
Code
#include <vector>
#include <queue>
#include <numeric>
using namespace std;
class Solution {
public:
bool canTraverseAllPairs(vector<int>& nums) {
int n = nums.size();
if (n == 1) return true;
// Build adjacency list by checking all pairs
vector<vector<int>> adj(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (__gcd(nums[i], nums[j]) > 1) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
// BFS to check connectivity
vector<bool> visited(n, false);
queue<int> q;
q.push(0);
visited[0] = true;
int count = 1;
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
count++;
q.push(neighbor);
}
}
}
return count == n;
}
};from math import gcd
from collections import deque
from typing import List
class Solution:
def canTraverseAllPairs(self, nums: List[int]) -> bool:
n = len(nums)
if n == 1:
return True
# Build adjacency list by checking all pairs
adj = [[] for _ in range(n)]
for i in range(n):
for j in range(i + 1, n):
if gcd(nums[i], nums[j]) > 1:
adj[i].append(j)
adj[j].append(i)
# BFS to check connectivity
visited = set([0])
queue = deque([0])
while queue:
node = queue.popleft()
for neighbor in adj[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return len(visited) == nimport java.util.*;
class Solution {
public boolean canTraverseAllPairs(int[] nums) {
int n = nums.length;
if (n == 1) return true;
// Build adjacency list by checking all pairs
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (gcd(nums[i], nums[j]) > 1) {
adj.get(i).add(j);
adj.get(j).add(i);
}
}
}
// BFS to check connectivity
boolean[] visited = new boolean[n];
Queue<Integer> queue = new LinkedList<>();
queue.offer(0);
visited[0] = true;
int count = 1;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
count++;
queue.offer(neighbor);
}
}
}
return count == n;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}Complexity Analysis
Time Complexity: O(n² × log(max(nums)))
We check all n×(n-1)/2 pairs, and for each pair we compute GCD in O(log(max(nums))) time using the Euclidean algorithm. The BFS runs in O(n + E) where E can be up to O(n²) edges. With n up to 10^5, this gives about 5×10^9 GCD operations — far too slow.
Space Complexity: O(n²)
The adjacency list can store up to O(n²) edges in the worst case where every pair shares a common factor. The visited array uses O(n) space.
Why This Approach Is Not Efficient
The brute force checks all O(n²) pairs of elements, computing GCD for each. With n up to 10^5, that is about 5 × 10^9 pair-checks — well beyond the typical time limit of 10^8 operations per second.
The deeper issue is that we are treating connectivity as a pairwise problem. But connectivity is transitive: if index A connects to index B, and B connects to C, then A can reach C. We do not need to explicitly discover every direct edge — we just need to group indices that share common factors.
Key insight: Two numbers share a common factor greater than 1 if and only if they share at least one prime factor. Instead of comparing every pair of numbers, we can use prime factors as "bridge nodes." If nums[i] has prime factor p, connect index i to the prime p. Any two indices that share a prime automatically land in the same connected component — without ever computing their GCD directly.
Using Union-Find (Disjoint Set Union) to track these connections gives us near-linear time.
Optimal Approach - Prime Factorization + Union-Find
Intuition
Instead of asking "do these two numbers share a common factor?" for every pair, we flip the perspective and ask "which indices share this particular prime factor?"
Imagine you are at a party. Instead of individually asking every pair of people whether they share a hobby, you set up tables for each hobby. Everyone who enjoys chess sits at the chess table, everyone who enjoys painting sits at the painting table. Now, anyone at the same table is automatically connected. If Alice is at both the chess and painting tables, then everyone at the chess table is connected to everyone at the painting table — through Alice.
The primes are our "hobby tables." For each number in the array, we find its prime factors and union the index with each prime factor node. If nums[0] = 6 (primes 2, 3), we union index 0 with prime-node 2 and prime-node 3. If nums[1] = 10 (primes 2, 5), we union index 1 with prime-node 2 and prime-node 5. Since both index 0 and index 1 connected to prime-node 2, they end up in the same component.
We use Union-Find (DSU) to efficiently track these merges. The Union-Find structure includes both the array indices (0 to n-1) and the prime numbers (offset by n to avoid ID collisions). After processing all numbers, we simply check whether all array indices share the same root.
Edge case: if any element is 1, it has no prime factors and can never connect to anything. So if n > 1 and any nums[i] = 1, the answer is immediately false.
Step-by-Step Explanation
Let's trace through nums = [4, 3, 12, 8].
Step 1: Initialize Union-Find with enough nodes for both indices (0-3) and potential primes. Compute prime factorizations: 4 = [2], 3 = [3], 12 = [2, 3], 8 = [2].
Step 2: Process index 0 (value 4, primes [2]).
- Union(index 0, prime 2). Now index 0 and prime-node 2 are in the same component.
- Components: {0, p2}, {1}, {2}, {3}, {p3}
Step 3: Process index 1 (value 3, primes [3]).
- Union(index 1, prime 3). Now index 1 and prime-node 3 are together.
- Components: {0, p2}, {1, p3}, {2}, {3}
Step 4: Process index 2 (value 12, primes [2, 3]).
- Union(index 2, prime 2). Prime 2 is already connected to index 0, so index 2 joins that component.
- Components: {0, p2, 2}, {1, p3}, {3}
- Union(index 2, prime 3). Prime 3 is connected to index 1. Merging connects both components.
- Components: {0, p2, 2, 1, p3}, {3}
Step 5: Process index 3 (value 8, primes [2]).
- Union(index 3, prime 2). Prime 2 is in the big component. Index 3 joins it.
- Components: {0, p2, 2, 1, p3, 3}
Step 6: Check connectivity: find root for each index 0-3. All have the same root → return true.
Counter-example: nums = [3, 9, 5]:
- Primes: 3=[3], 9=[3], 5=[5]
- After processing: {0, p3, 1} and {2, p5} — two separate components.
- Not all indices share same root → return false.
Prime Factor Union-Find — Connecting Indices Through Shared Primes — Watch how we factorize each number and union its index with prime-factor nodes, gradually merging all indices into one connected component.
Algorithm
- Handle edge cases: if n == 1, return true. If any element equals 1 and n > 1, return false (1 has no prime factors and can never connect to anything).
- Initialize a Union-Find structure with n + max(nums) + 1 elements. Indices 0 to n-1 represent array positions. Indices n onwards represent prime numbers (prime p is stored at position p + n).
- For each element nums[i]:
a. Compute its prime factorization by trial division up to √nums[i].
b. For each prime factor p, call union(i, p + n) to connect the index with the prime-factor node. - After processing all elements, check how many unique roots exist among indices 0 to n-1.
- If there is exactly 1 unique root, all indices are connected → return true. Otherwise → return false.
Code
#include <vector>
#include <numeric>
#include <unordered_set>
using namespace std;
class UnionFind {
public:
vector<int> parent, size;
UnionFind(int n) : parent(n), size(n, 1) {
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 a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return;
if (size[ra] < size[rb]) swap(ra, rb);
parent[rb] = ra;
size[ra] += size[rb];
}
};
class Solution {
public:
bool canTraverseAllPairs(vector<int>& nums) {
int n = nums.size();
if (n == 1) return true;
int mx = *max_element(nums.begin(), nums.end());
UnionFind uf(n + mx + 1);
for (int i = 0; i < n; i++) {
if (nums[i] == 1) return false;
int val = nums[i];
for (int d = 2; d * d <= val; d++) {
if (val % d == 0) {
uf.unite(i, d + n);
while (val % d == 0) val /= d;
}
}
if (val > 1) uf.unite(i, val + n);
}
unordered_set<int> roots;
for (int i = 0; i < n; i++)
roots.insert(uf.find(i));
return roots.size() == 1;
}
};from typing import List
class UnionFind:
def __init__(self, n: int):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x: int) -> int:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, a: int, b: int) -> None:
ra, rb = self.find(a), self.find(b)
if ra == rb:
return
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
class Solution:
def canTraverseAllPairs(self, nums: List[int]) -> bool:
n = len(nums)
if n == 1:
return True
mx = max(nums)
uf = UnionFind(n + mx + 1)
for i, val in enumerate(nums):
if val == 1:
return False
d = 2
temp = val
while d * d <= temp:
if temp % d == 0:
uf.union(i, d + n)
while temp % d == 0:
temp //= d
d += 1
if temp > 1:
uf.union(i, temp + n)
roots = set(uf.find(i) for i in range(n))
return len(roots) == 1import java.util.*;
class Solution {
int[] parent, size;
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
void union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return;
if (size[ra] < size[rb]) {
int temp = ra; ra = rb; rb = temp;
}
parent[rb] = ra;
size[ra] += size[rb];
}
public boolean canTraverseAllPairs(int[] nums) {
int n = nums.length;
if (n == 1) return true;
int mx = 0;
for (int num : nums) mx = Math.max(mx, num);
parent = new int[n + mx + 1];
size = new int[n + mx + 1];
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
size[i] = 1;
}
for (int i = 0; i < n; i++) {
if (nums[i] == 1) return false;
int val = nums[i];
for (int d = 2; d * d <= val; d++) {
if (val % d == 0) {
union(i, d + n);
while (val % d == 0) val /= d;
}
}
if (val > 1) union(i, val + n);
}
Set<Integer> roots = new HashSet<>();
for (int i = 0; i < n; i++)
roots.add(find(i));
return roots.size() == 1;
}
}Complexity Analysis
Time Complexity: O(n × √M × α(n + M))
Where n is the array length and M = max(nums).
- For each of the n elements, prime factorization by trial division takes O(√M) time.
- Each prime factor triggers a union operation. A number has at most O(log M) prime factors, and each union takes amortized O(α(n + M)) time, where α is the inverse Ackermann function (practically constant).
- The final connectivity check iterates through n elements with find operations.
- Total: O(n × √M) dominates, which is roughly O(10^5 × 316) ≈ 3 × 10^7 — well within time limits.
Space Complexity: O(n + M)
The Union-Find structure stores n + M + 1 elements for the parent and size arrays. This is the dominant space cost. With M up to 10^5 and n up to 10^5, the total space is about 2 × 10^5.