2709. Greatest Common Divisor Traversal
Problem Description
In this problem, we have an array of integers called nums
. The array is 0-indexed, which means the indices of the array start at 0. We are tasked with a traversal problem where we can move from one index to another under certain conditions. Specifically, we can move from index i
to index j
if and only if the greatest common divisor (gcd
) of nums[i]
and nums[j]
is greater than 1. The goal is to determine if it is possible to move between every pair of indices i
and j
, where i < j
, through a series of such allowed traversals.
To be more precise, for any two elements at indices i
and j
, we want to know if there's a way to start at i
and get to j
by jumping between indices, where at each step the gcd
of the values at those indices is greater than 1. If it's possible to do so for all such pairs, we return true
; otherwise, we return false
.
Intuition
The problem at its core is a connectivity problem. We want to know if every number is connected to every other number through a series of gcd relationships that are greater than 1. A natural approach to problems involving connectivity is to use a Disjoint Set Union (DSU) or Union-Find data structure which efficiently handles 'union' and 'find' operations to determine if elements are connected.
The intuition behind the solution lies in considering each unique prime factor that divides numbers in nums
as a 'connection point'. If two numbers share a prime factor, they are directly connected. We model the problem as a graph where each index of nums
and each unique prime factor represents nodes. An edge exists between an index and a prime factor node if the number at that index is divisible by that prime factor.
To implement this, we use a Union-Find data structure. First, we precompute the prime factors for all numbers up to the maximum value in nums
. Then, for each number in nums
, we join (union) its index with the nodes corresponding to its prime factors.
After processing all numbers, we check the parents of all indices in the Union-Find structure. If all numbers are connected, there should be only one unique parent among them. If that's the case, we return true
, indicating it's possible to traverse between all pairs of indices as required by the problem. If there are multiple unique parents, we return false
since that means not all numbers are connected.
Learn more about Union Find and Math patterns.
Solution Approach
The solution approach utilizes the Union-Find data structure to track the connectivity between indices of the array based on common prime factors of their values. Let's walk through the key steps of the implementation:
-
We define a Union-Find class (also known as a Disjoint Set Union (DSU)) that includes mechanisms to union two sets and to find the representative (or parent) of a set.
-
__init__
: Initialize two lists,self.p
to keep track of each node's parent andself.size
to record the size of each set. At the start, each node is its own parent and the size of each set is 1. -
find
: This method compresses the path for any node, by recursively finding its ultimate parent, and also performs path compression to flatten the structure for efficiency. -
union
: It unites two sets by connecting their roots. We attach the smaller set to the larger one to keep the tree shallow, which helps in keeping thefind
operation fast.
-
-
We precompute all prime factors for all numbers up to the maximum value found in
nums
using a trial division algorithm. This precomputation is done outside of theSolution
class. A defaultdictp
is used to store a list of prime factors for each number. -
Within our main
Solution
class, thecanTraverseAllPairs
function implements the primary logic:-
We first instantiate our
UnionFind
class with enough nodes for all indices innums
and all potential prime factors (up to the maximum number innums
). -
We then iterate over each number in
nums
. For each numberx
, we fetch its previously computed list of prime factors. For each prime factorj
, we union the current indexi
with the node corresponding toj + n
. The offset byn
is used to distinguish between index nodes and prime factor nodes in our Union-Find structure. -
Finally, after all unions are performed, we check the parent of every index. If all indices have the same parent, we return
true
. This would imply that all indices are connected via their common prime factors, and hence, it is possible to traverse from any index to any other index (as long asi < j
). Otherwise, we returnfalse
, indicating that there are indices that are not connected.
-
With the prime factorization and the DSU algorithm, our solution efficiently determines the connectivity of the array indices based on the rule that gcd(nums[i], nums[j]) > 1
.
In summary, this solution leverages the Union-Find data structure to solve a graph connectivity problem by interpreting prime factor sharing as a connectivity criterion between indices in an integer array.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a simple example. Suppose we have an array nums
given as [6, 10, 15]
. To determine if we can traverse from any index to any other index as long as their gcd is greater than 1, we follow these steps:
-
We initialize the Union-Find class for our three elements
[6, 10, 15]
. This means we start with each element being its own parent. Suppose our Union-Find internal array looks like this (where index and value paired represent a node and its parent):[0, 1, 2] (initial parent list)
-
Next, we precompute the prime factors for numbers up to the maximum value in
nums
, which is 15. So our prime factor list may look something like this:- 6: [2, 3]
- 10: [2, 5]
- 15: [3, 5]
-
We now iterate through our
nums
array and union indices based on their prime factors. We offset the prime factor numbers by the length ofnums
, which is 3 in this case, to differentiate them from the index nodes:- For
6
at index0
, we have prime factors [2, 3].- Union(0, 2+3) and Union(0, 3+3) -> Connect 0 with nodes at index 5 and 6.
- For
10
at index1
, we have prime factors [2, 5].- Union(1, 2+3) and Union(1, 5+3) -> Connect 1 with nodes at index 5 and 8.
- For
15
at index2
, we have prime factors [3, 5].- Union(2, 3+3) and Union(2, 5+3) -> Connect 2 with nodes at index 6 and 8.
After the Union operations, the internal parent array may look something like this:
[0, 0, 0, 3, 3, 0, 0, 5, 0] (updated parent list)
- For
-
Finally, we check if all indices in
nums
are connected by comparing their parent nodes. In this example, indices0
,1
, and2
are all connected to the same parent index0
, which means they are all in the same set and there is a way to traverse between every pair of indices with gcd greater than 1.
Since all elements can reach each other through their shared prime factors, the function canTraverseAllPairs
would return true
for this example.
Explanation
By using the Union-Find data structure, we analyze the connectivity of our array's indices based on shared prime factors. In the given example, we successfully showed that each element in the array nums
could be traversed to any other element, meeting the problem's requirement because of the prime factors they share (2, 3, and 5), allowing for the traversal between indices to occur. This satisfies the condition for gcd being greater than 1 for all pairs.
Solution Implementation
1from collections import defaultdict
2
3class UnionFind:
4 def __init__(self, size):
5 self.parents = list(range(size))
6 self.sizes = [1] * size
7
8 def find(self, node):
9 # Recursively find the root of the node and perform path compression
10 if self.parents[node] != node:
11 self.parents[node] = self.find(self.parents[node])
12 return self.parents[node]
13
14 def union(self, node_a, node_b):
15 # Merge the groups containing node_a and node_b
16 root_a, root_b = self.find(node_a), self.find(node_b)
17 if root_a == root_b:
18 return False # Already in the same set
19
20 # Union by size: attach the smaller tree to the root of the larger tree
21 if self.sizes[root_a] > self.sizes[root_b]:
22 self.parents[root_b] = root_a
23 self.sizes[root_a] += self.sizes[root_b]
24 else:
25 self.parents[root_a] = root_b
26 self.sizes[root_b] += self.sizes[root_a]
27 return True
28
29
30# Max value to be considered for factoring the numbers
31max_value = 100010
32
33# Dictionary to hold prime factors for each number
34prime_factors = defaultdict(list)
35
36# Pre-calculate prime factors for all numbers up to max_value
37for number in range(1, max_value + 1):
38 value = number
39 factor = 2
40 while factor <= value // factor:
41 if value % factor == 0:
42 prime_factors[number].append(factor)
43 while value % factor == 0:
44 value //= factor
45 factor += 1
46 if value > 1:
47 prime_factors[number].append(value)
48
49class Solution:
50 def canTraverseAllPairs(self, nums):
51 # Count the numbers and find the maximum number
52 count = len(nums)
53 max_num = max(nums)
54
55 # Create a UnionFind instance
56 uf = UnionFind(count + max_num + 1)
57
58 # Union numbers with their prime factors
59 for i, num in enumerate(nums):
60 for prime in prime_factors[num]:
61 uf.union(i, prime + count)
62
63 # Check if all numbers are connected (in the same set)
64 root_set = {uf.find(i) for i in range(count)}
65 return len(root_set) == 1
66
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.HashSet;
4import java.util.List;
5import java.util.Set;
6
7class UnionFind {
8 private int[] parent;
9 private int[] size;
10
11 // Constructor initializes the Union-Find data structure
12 public UnionFind(int n) {
13 parent = new int[n];
14 size = new int[n];
15 for (int i = 0; i < n; ++i) {
16 parent[i] = i; // Each node is initially its own parent
17 size[i] = 1; // Initial size of each set is 1
18 }
19 }
20
21 // Find the root of the set that element x belongs to
22 public int find(int x) {
23 if (parent[x] != x) {
24 parent[x] = find(parent[x]); // Path compression for efficiency
25 }
26 return parent[x];
27 }
28
29 // Union of two sets represented by elements a and b
30 public boolean union(int a, int b) {
31 int rootA = find(a);
32 int rootB = find(b);
33
34 if (rootA == rootB) {
35 // Elements are already in the same set
36 return false;
37 }
38
39 // Merge two sets by comparing their sizes to maintain a balanced tree
40 if (size[rootA] > size[rootB]) {
41 parent[rootB] = rootA; // Attach the smaller tree's root to the larger tree's root
42 size[rootA] += size[rootB]; // Update the size of the resulting tree
43 } else {
44 parent[rootA] = rootB;
45 size[rootB] += size[rootA];
46 }
47 return true;
48 }
49}
50
51class Solution {
52 private static final int MAX_NUM = 100010;
53 private static final List<Integer>[] primeFactors = new List[MAX_NUM];
54
55 // Static block for initialization of prime factor lists for numbers up to MAX_NUM
56 static {
57 Arrays.setAll(primeFactors, x -> new ArrayList<>());
58 for (int num = 1; num < MAX_NUM; ++num) {
59 int temp = num;
60 for (int i = 2; i <= temp / i; ++i) {
61 if (temp % i == 0) {
62 primeFactors[num].add(i);
63 while (temp % i == 0) {
64 temp /= i;
65 }
66 }
67 }
68 if (temp > 1) {
69 primeFactors[num].add(temp); // Add remaining prime factor
70 }
71 }
72 }
73
74 // Method to check if it's possible to traverse all pairs of indices in the array nums
75 public boolean canTraverseAllPairs(int[] nums) {
76 //_maxValue holds the maximum value in nums
77 int maxValue = Arrays.stream(nums).max().getAsInt();
78 int n = nums.length;
79
80 // Create a UnionFind object to represent graph connectivity
81 UnionFind unionFind = new UnionFind(n + maxValue + 1);
82
83 // Union each number with its prime factors offset by n (to avoid index collision)
84 for (int i = 0; i < n; ++i) {
85 for (int prime : primeFactors[nums[i]]) {
86 unionFind.union(i, prime + n);
87 }
88 }
89
90 // Add the root representative of each number to a set to check connectivity
91 Set<Integer> roots = new HashSet<>();
92 for (int i = 0; i < n; ++i) {
93 roots.add(unionFind.find(i));
94 }
95
96 // If there is only one root, all nodes are connected
97 return roots.size() == 1;
98 }
99}
100
101// Usage example (not part of the solution):
102// You can now create a `Solution` object and call the `canTraverseAllPairs` method with an array of numbers
103
1#include <vector>
2#include <numeric>
3#include <algorithm>
4#include <unordered_set>
5using namespace std;
6
7// Define a constant size for the array of vectors
8const int MAX_VALUE = 100010;
9vector<int> prime_factors[MAX_VALUE];
10
11// Lambda function to initialize the prime factors for each number up to MAX_VALUE
12int init = []() {
13 for (int x = 1; x < MAX_VALUE; ++x) {
14 int value = x;
15 int divisor = 2;
16 while (divisor <= value / divisor) {
17 if (value % divisor == 0) {
18 prime_factors[x].push_back(divisor);
19 while (value % divisor == 0) {
20 value /= divisor;
21 }
22 }
23 ++divisor;
24 }
25 if (value > 1) {
26 prime_factors[x].push_back(value);
27 }
28 }
29 return 0;
30}();
31
32// Class to represent a Union-Find data structure
33class UnionFind {
34public:
35 // Constructor initializes Union-Find with n elements
36 UnionFind(int n): parent(n), rank(n, 1), count(n) {
37 iota(parent.begin(), parent.end(), 0);
38 }
39
40 // Method to merge two sets; returns true if a merge happened, false if already united
41 bool unite(int a, int b) {
42 int rootA = find(a), rootB = find(b);
43 if (rootA == rootB) {
44 return false;
45 }
46 // Union by rank
47 if (rank[rootA] > rank[rootB]) {
48 parent[rootB] = rootA;
49 rank[rootA] += rank[rootB];
50 } else {
51 parent[rootA] = rootB;
52 rank[rootB] += rank[rootA];
53 }
54 --count;
55 return true;
56 }
57
58 // Method to find the root of the set that element x belongs to
59 int find(int x) {
60 if (parent[x] != x) {
61 parent[x] = find(parent[x]); // Path compression
62 }
63 return parent[x];
64 }
65
66 // Get the current number of disjoint sets
67 int getCount() const {
68 return count;
69 }
70
71private:
72 // Private members to keep track of the parents and the size of each tree
73 vector<int> parent, rank;
74 int count; // Number of disjoint sets
75};
76
77// Class with a method to solve the problem
78class Solution {
79public:
80 // Method to determine if all pairs in the nums vector can traverse via their prime factors
81 bool canTraverseAllPairs(vector<int>& nums) {
82 int maxNum = *max_element(nums.begin(), nums.end());
83 int size = nums.size();
84 UnionFind uf(maxNum + size + 1);