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.
1#include <iostream>
2#include <vector>
3using namespace std;
4
5class UnionFind {
6public:
7 vector<int> root;
8 vector<int> rank;
9
10 UnionFind(int size) {
11 root.resize(size);
12 rank.resize(size, 1);
13 for (int i = 0; i < size; ++i) {
14 root[i] = i;
15 }
16 }
17
18 int find(int x) {
19 if (root[x] == x) return x;
20 return root[x] = find(root[x]);
21 }
22
23 void unionSet(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
39int gcd(int a, int b) {
40 while (b != 0) {
41 int t = b;
42 b = a % b;
43 a = t;
44 }
45 return a;
46}
47
48bool canTraverseAllPairs(vector<int>& nums) {
49 int n = nums.size();
50 UnionFind uf(n);
51 for (int i = 0; i < n; ++i) {
52 for (int j = i + 1; j < n; ++j) {
53 if (gcd(nums[i], nums[j]) > 1) {
54 uf.unionSet(i, j);
55 }
56 }
57 }
58 int root = uf.find(0);
59 for (int i = 1; i < n; ++i) {
60 if (uf.find(i) != root) return false;
61 }
62 return true;
63}
64
65int main() {
66 vector<int> nums = {2, 3, 6};
67 cout << (canTraverseAllPairs(nums) ? "true" : "false") << endl;
68 return 0;
69}
70Similar to the C implementation, this C++ code uses a Union-Find class to manage the connections between indices. It finds and unions indices with a GCD greater than 1, checking if all indices end up in the same component.
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.