Sponsored
Sponsored
This approach considers the integer array as a graph where each index is a node. We connect nodes i and j if gcd(nums[i], nums[j]) > 1. Using a union-find data structure, we efficiently manage connected components as we establish connections among indices. The goal is to determine whether all indices are part of a single connected component.
The time complexity is O(n^2 * log*(n)), due to the nested for loops for each pair of numbers, where log* is the inverse Ackermann function that represents the amortized time of the union-find operations. The space complexity is O(n) for storing the union-find array.
1class UnionFind {
2 constructor(size) {
3 this.root = Array.from({ length: size }, (_, i) => i);
4 this.rank = Array(size).fill(1);
5 }
6
7 find(x) {
8 if (this.root[x] !== x) {
9 this.root[x] = this.find(this.root[x]);
10 }
11 return this.root[x];
12 }
13
14 union(x, y) {
15 const rootX = this.find(x);
16 const rootY = this.find(y);
17 if (rootX !== rootY) {
18 if (this.rank[rootX] > this.rank[rootY]) {
19 this.root[rootY] = rootX;
20 } else if (this.rank[rootX] < this.rank[rootY]) {
21 this.root[rootX] = rootY;
22 } else {
23 this.root[rootY] = rootX;
24 this.rank[rootX]++;
25 }
26 }
27 }
28}
29
30function gcd(a, b) {
31 while (b !== 0) {
32 [a, b] = [b, a % b];
33 }
34 return a;
35}
36
37function canTraverseAllPairs(nums) {
38 const n = nums.length;
39 const uf = new UnionFind(n);
40
41 for (let i = 0; i < n; i++) {
42 for (let j = i + 1; j < n; j++) {
43 if (gcd(nums[i], nums[j]) > 1) {
44 uf.union(i, j);
45 }
46 }
47 }
48
49 const root = uf.find(0);
50 for (let i = 1; i < n; i++) {
51 if (uf.find(i) !== root) {
52 return false;
53 }
54 }
55
56 return true;
57}
58
59console.log(canTraverseAllPairs([2, 3, 6]));
60This JavaScript code applies the union-find technique to address index connectivity through GCD-based connections. Each index connects by pairwise calculations, and a complete traversal check ensures if all can join via a single subset.
In this approach, the solution represents the integer array as an adjacency list graph. Each index is considered as a node, and we link them with edges if their GCD is greater than 1. We perform a depth-first search (DFS) or breadth-first search (BFS) to determine the connectivity of the nodes. If all indices are reachable from any starting index, the traversal is possible.
The time complexity is O(n^2), and the space complexity also is O(n^2) due to the adjacency matrix representation.
This C code constructs a graph using an adjacency matrix. It uses DFS to check connectivity from the first index to all others, ensuring all indices are reachable.