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 <stdio.h>
2#include <stdlib.h>
3
4int find(int* parents, int x) {
5 if (parents[x] != x) {
6 parents[x] = find(parents, parents[x]);
7 }
8 return parents[x];
9}
10
11void union_sets(int* parents, int* rank, int x, int y) {
12 int rootX = find(parents, x);
13 int rootY = find(parents, y);
14 if (rootX != rootY) {
15 if (rank[rootX] > rank[rootY]) {
16 parents[rootY] = rootX;
17 } else if (rank[rootX] < rank[rootY]) {
18 parents[rootX] = rootY;
19 } else {
20 parents[rootY] = rootX;
21 rank[rootX]++;
22 }
23 }
24}
25
26int gcd(int a, int b) {
27 while (b != 0) {
28 int t = b;
29 b = a % b;
30 a = t;
31 }
32 return a;
33}
34
35int canTraverseAllPairs(int* nums, int numsSize) {
36 int* parents = (int*)malloc(numsSize * sizeof(int));
37 int* rank = (int*)calloc(numsSize, sizeof(int));
38
39 for (int i = 0; i < numsSize; i++) {
40 parents[i] = i;
41 }
42
43 for (int i = 0; i < numsSize; i++) {
44 for (int j = i + 1; j < numsSize; j++) {
45 if (gcd(nums[i], nums[j]) > 1) {
46 union_sets(parents, rank, i, j);
47 }
48 }
49 }
50
51 int root = find(parents, 0);
52 for (int i = 1; i < numsSize; i++) {
53 if (find(parents, i) != root) {
54 free(parents);
55 free(rank);
56 return 0;
57 }
58 }
59
60 free(parents);
61 free(rank);
62 return 1;
63}
64
65int main() {
66 int nums[] = {2, 3, 6};
67 int numsSize = sizeof(nums) / sizeof(nums[0]);
68 printf("%s\n", canTraverseAllPairs(nums, numsSize) ? "true" : "false");
69 return 0;
70}
71This C code uses the union-find algorithm to determine the connectivity of an array. We initialize unconnected components for each element, then iterate through the elements, connecting them if their GCD is greater than 1. If all elements share the same root parent after processing, they belong to a single connected component, implying that traversal is possible between every index.
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.
1#include <vector>
using namespace std;
int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
void dfs(int v, vector<vector<int>>& adj, vector<bool>& visited) {
visited[v] = true;
for (int u : adj[v]) {
if (!visited[u]) {
dfs(u, adj, visited);
}
}
}
bool canTraverseAllPairs(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> adj(n);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (gcd(nums[i], nums[j]) > 1) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
vector<bool> visited(n, false);
dfs(0, adj, visited);
for (bool v : visited) {
if (!v) return false;
}
return true;
}
int main() {
vector<int> nums = {2, 3, 6};
cout << (canTraverseAllPairs(nums) ? "true" : "false") << endl;
return 0;
}
This C++ solution builds an adjacency list graph and performs DFS to verify if all vertices (indices) are reachable from the starting index, thereby ensuring connectivity.