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.
The Python code represents the array as an adjacency list graph, performing DFS to check whether all nodes are reachable from the first one, verifying the traversal capability between indices.