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.
1using System;
2
3public class UnionFind {
4 private int[] root;
5 private int[] rank;
6
7 public UnionFind(int size) {
8 root = new int[size];
9 rank = new int[size];
10 for (int i = 0; i < size; i++) {
11 root[i] = i;
12 rank[i] = 1;
13 }
14 }
15
16 public int Find(int x) {
17 if (x == root[x]) {
18 return x;
19 }
20 return root[x] = Find(root[x]);
21 }
22
23 public void Union(int x, int y) {
24 int rootX = Find(x);
25 int rootY = Find(y);
26 if (rootX != rootY) {
27 if (rank[rootX] > rank[rootY]) {
28 root[rootY] = rootX;
29 } else if (rank[rootX] < rank[rootY]) {
30 root[rootX] = rootY;
31 } else {
32 root[rootY] = rootX;
33 rank[rootX]++;
34 }
35 }
36 }
37}
38
39public class Solution {
40 private int Gcd(int a, int b) {
41 while (b != 0) {
42 int t = b;
43 b = a % b;
44 a = t;
45 }
46 return a;
47 }
48
49 public bool CanTraverseAllPairs(int[] nums) {
50 int n = nums.Length;
51 UnionFind uf = new UnionFind(n);
52
53 for (int i = 0; i < n; i++) {
54 for (int j = i + 1; j < n; j++) {
55 if (Gcd(nums[i], nums[j]) > 1) {
56 uf.Union(i, j);
57 }
58 }
59 }
60 int root = uf.Find(0);
61 for (int i = 1; i < n; i++) {
62 if (uf.Find(i) != root) {
63 return false;
64 }
65 }
66 return true;
67 }
68
69 public static void Main() {
70 Solution sol = new Solution();
71 int[] nums = new int[] {2, 3, 6};
72 Console.WriteLine(sol.CanTraverseAllPairs(nums));
73 }
74}
75This 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.
using System.Collections.Generic;
public class Solution {
private int Gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
private void Dfs(int node, List<int>[] adj, bool[] visited) {
visited[node] = true;
foreach (int neighbor in adj[node]) {
if (!visited[neighbor]) {
Dfs(neighbor, adj, visited);
}
}
}
public bool CanTraverseAllPairs(int[] nums) {
int n = nums.Length;
List<int>[] adj = new List<int>[n];
for (int i = 0; i < n; i++) {
adj[i] = new List<int>();
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (Gcd(nums[i], nums[j]) > 1) {
adj[i].Add(j);
adj[j].Add(i);
}
}
}
bool[] visited = new bool[n];
Dfs(0, adj, visited);
foreach (bool v in visited) {
if (!v) {
return false;
}
}
return true;
}
public static void Main() {
int[] nums = new int[] {2, 3, 6};
Solution sol = new Solution();
Console.WriteLine(sol.CanTraverseAllPairs(nums));
}
}
This C# solution creates an adjacency list and executes a depth-first search to confirm connectivity from the first index to all others.