Facebook Pixel

2709. Greatest Common Divisor Traversal

HardUnion FindArrayMathNumber Theory
Leetcode Link

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:

  1. 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 and self.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 the find operation fast.

  2. 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 the Solution class. A defaultdict p is used to store a list of prime factors for each number.

  3. Within our main Solution class, the canTraverseAllPairs function implements the primary logic:

    • We first instantiate our UnionFind class with enough nodes for all indices in nums and all potential prime factors (up to the maximum number in nums).

    • We then iterate over each number in nums. For each number x, we fetch its previously computed list of prime factors. For each prime factor j, we union the current index i with the node corresponding to j + n. The offset by n 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 as i < j). Otherwise, we return false, 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 Evaluator

Example 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:

  1. 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)

  2. 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]

  3. We now iterate through our nums array and union indices based on their prime factors. We offset the prime factor numbers by the length of nums, which is 3 in this case, to differentiate them from the index nodes:

    • For 6 at index 0, 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 index 1, 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 index 2, 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)

  4. Finally, we check if all indices in nums are connected by comparing their parent nodes. In this example, indices 0, 1, and 2 are all connected to the same parent index 0, 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);