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.
This JavaScript code applies the union-find technique to address index connectivity through GCD-based connections. Each index connects by pairwise calculations, and a complete traversal check ensures if all can join via a single subset.
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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 private int Gcd(int a, int b) {
6 while (b != 0) {
7 int t = b;
8 b = a % b;
9 a = t;
10 }
11 return a;
12 }
13
14 private void Dfs(int node, List<int>[] adj, bool[] visited) {
15 visited[node] = true;
16 foreach (int neighbor in adj[node]) {
17 if (!visited[neighbor]) {
18 Dfs(neighbor, adj, visited);
19 }
20 }
21 }
22
23 public bool CanTraverseAllPairs(int[] nums) {
24 int n = nums.Length;
25 List<int>[] adj = new List<int>[n];
26 for (int i = 0; i < n; i++) {
27 adj[i] = new List<int>();
28 }
29
30 for (int i = 0; i < n; i++) {
31 for (int j = i + 1; j < n; j++) {
32 if (Gcd(nums[i], nums[j]) > 1) {
33 adj[i].Add(j);
34 adj[j].Add(i);
35 }
36 }
37 }
38
39 bool[] visited = new bool[n];
40 Dfs(0, adj, visited);
41
42 foreach (bool v in visited) {
43 if (!v) {
44 return false;
45 }
46 }
47 return true;
48 }
49
50 public static void Main() {
51 int[] nums = new int[] {2, 3, 6};
52 Solution sol = new Solution();
53 Console.WriteLine(sol.CanTraverseAllPairs(nums));
54 }
55}
56This C# solution creates an adjacency list and executes a depth-first search to confirm connectivity from the first index to all others.