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.
public class UnionFind {
private int[] root;
private int[] rank;
public UnionFind(int size) {
root = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
root[i] = i;
rank[i] = 1;
}
}
public int Find(int x) {
if (x == root[x]) {
return x;
}
return root[x] = Find(root[x]);
}
public void Union(int x, int y) {
int rootX = Find(x);
int rootY = Find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
root[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
root[rootX] = rootY;
} else {
root[rootY] = rootX;
rank[rootX]++;
}
}
}
}
public class Solution {
private int Gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
public bool CanTraverseAllPairs(int[] nums) {
int n = nums.Length;
UnionFind uf = new UnionFind(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (Gcd(nums[i], nums[j]) > 1) {
uf.Union(i, j);
}
}
}
int root = uf.Find(0);
for (int i = 1; i < n; i++) {
if (uf.Find(i) != root) {
return false;
}
}
return true;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = new int[] {2, 3, 6};
Console.WriteLine(sol.CanTraverseAllPairs(nums));
}
}
This C# solution utilizes the union-find method to check the connectivity amongst indices. By ensuring that pairwise GCDs form connections, the code determines any traversal possibility via a single component check.
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.
1function gcd(a, b) {
2 while (b !== 0) {
3 [a, b] = [b, a % b];
4 }
5 return a;
6}
7
8function canTraverseAllPairs(nums) {
9 const n = nums.length;
10 const adj = Array.from({ length: n }, () => []);
11
12 for (let i = 0; i < n; i++) {
13 for (let j = i + 1; j < n; j++) {
14 if (gcd(nums[i], nums[j]) > 1) {
15 adj[i].push(j);
16 adj[j].push(i);
17 }
18 }
19 }
20
21 const visited = new Array(n).fill(false);
22
23 function dfs(v) {
24 visited[v] = true;
25 for (const u of adj[v]) {
26 if (!visited[u]) {
27 dfs(u);
28 }
29 }
30 }
31
32 dfs(0);
33
34 return visited.every(Boolean);
35}
36
37console.log(canTraverseAllPairs([2, 3, 6]));
38This JavaScript code implements a graph traversal using DFS built on an adjacency list. It verifies if all indices form a connected component, allowing traversal between any two indices based on their GCDs.