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.
1def find(parents, i):
2 if parents[i] != i:
3 parents[i] = find(parents, parents[i])
4 return parents[i]
5
6
7def union(parents, rank, x, y):
8 rootX = find(parents, x)
9 rootY = find(parents, y)
10 if rootX != rootY:
11 if rank[rootX] > rank[rootY]:
12 parents[rootY] = rootX
13 elif rank[rootX] < rank[rootY]:
14 parents[rootX] = rootY
15 else:
16 parents[rootY] = rootX
17 rank[rootX] += 1
18
19
20def gcd(x, y):
21 while y:
22 x, y = y, x % y
23 return x
24
25
26def can_traverse_all_pairs(nums):
27 n = len(nums)
28 parents = list(range(n))
29 rank = [0] * n
30
31 for i in range(n):
32 for j in range(i + 1, n):
33 if gcd(nums[i], nums[j]) > 1:
34 union(parents, rank, i, j)
35
36 root = find(parents, 0)
37 for i in range(1, n):
38 if find(parents, i) != root:
39 return False
40 return True
41
42
43if __name__ == "__main__":
44 nums = [2, 3, 6]
45 print(can_traverse_all_pairs(nums))
46This Python solution implements the union-find method, establishing connections among indices with pairwise GCDs greater than 1. It then checks if all elements form a single connected component by examining the root of each 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.
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.