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.
The Python code represents the array as an adjacency list graph, performing DFS to check whether all nodes are reachable from the first one, verifying the traversal capability between indices.