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.
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.