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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement priority queue?

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);
85
86        // Union sets based on shared prime factors
87        for (int i = 0; i < size; ++i) {
88            for (int factor : prime_factors[nums[i]]) {
89                uf.unite(i, factor + size);
90            }
91        }
92
93        // Check if all numbers are connected through their prime factors
94        unordered_set<int> distinctRoots;
95        for (int i = 0; i < size; ++i) {
96            distinctRoots.insert(uf.find(i));
97        }
98        // If there is only one distinct root, all numbers are connected
99        return distinctRoots.size() == 1;
100    }
101};
102
1// A constant size for the array of vectors, representing the maximum value
2const MAX_VALUE: number = 100010;
3const primeFactors: number[][] = Array.from({ length: MAX_VALUE }, () => []);
4
5// Initialize the prime factors for each number up to MAX_VALUE
6const initializePrimeFactors = () => {
7  for (let x = 1; x < MAX_VALUE; ++x) {
8    let value = x;
9    let divisor = 2;
10    while (divisor <= Math.floor(value / divisor)) {
11      if (value % divisor === 0) {
12        primeFactors[x].push_back(divisor);
13        while (value % divisor === 0) {
14          value /= divisor;
15        }
16      }
17      ++divisor;
18    }
19    if (value > 1) {
20      primeFactors[x].push(divisor);
21    }
22  }
23};
24initializePrimeFactors();
25
26// Variables to keep track of the parents and the size of each set
27let parent: number[] = [];
28let rank: number[] = [];
29let count: number = 0;
30
31// Function to initialize Union-Find with 'n' elements
32const createUnionFind = (n: number) => {
33  parent = Array.from({ length: n }, (_, i) => i);
34  rank = Array.from({ length: n }, () => 1);
35  count = n;
36};
37
38// Function to find the root of the set that element 'x' belongs to, with path compression
39const findSet = (x: number): number => {
40  if (parent[x] !== x) {
41    parent[x] = findSet(parent[x]);
42  }
43  return parent[x];
44};
45
46// Function to merge two sets; returns true if a merge happened, false if already united
47const uniteSets = (a: number, b: number): boolean => {
48  const rootA = findSet(a);
49  const rootB = findSet(b);
50  if (rootA === rootB) {
51    return false;
52  }
53  // Union by rank
54  if (rank[rootA] > rank[rootB]) {
55    parent[rootB] = rootA;
56    rank[rootA] += rank[rootB];
57  } else {
58    parent[rootA] = rootB;
59    rank[rootB] += rank[rootA];
60  }
61  --count;
62  return true;
63};
64
65// Function to determine if all pairs in the nums array can traverse via their prime factors
66const canTraverseAllPairs = (nums: number[]): boolean => {
67  const maxNum = Math.max(...nums);
68  const size = nums.length;
69  createUnionFind(maxNum + size + 1);
70
71  // Union sets based on shared prime factors
72  nums.forEach((num, i) => {
73    primeFactors[num].forEach(factor => {
74      uniteSets(i, factor + size);
75    });
76  });
77
78  // Check if all numbers are connected through their prime factors
79  const distinctRoots: Set<number> = new Set();
80  nums.forEach((_, i) => {
81    distinctRoots.add(findSet(i));
82  });
83  // If there is only one distinct root, all numbers are connected
84  return distinctRoots.size === 1;
85};
86
Not Sure What to Study? Take the 2-min Quiz：

Which of these pictures shows the visit order of a depth-first search?

Time and Space Complexity

Time Complexity

The time complexity of the code can be broken down as follows:

  • The initialization of the UnionFind class takes O(n) time, where n is the number of elements in the nums array. This is because it initializes two arrays of size n, p and size.

  • The nested loop outside the Solution class where the prime factors of numbers from 1 to mx are calculated has a time complexity of O(mx * sqrt(mx)). For each x, it finds factors by iterating up to the square root of x (v//i). In the worst case, this could be as high as O(mx * sqrt(mx)).

  • Inside the Solution class, the canTraverseAllPairs function iterates through the nums array once, hence O(n) where n is the length of nums.

  • For each number x in nums, it iterates over its prime factors. The number of iterations here depends on the number of prime factors a number has, which is bounded by O(log x) for a number x. However, since x can be up to mx, the number of prime factors can be considered O(log mx).

  • For each prime factor, the union operation is performed. The union-find union and find operations have a time complexity of O(log*(n + m)) with path compression, where n is the length of nums and m is the maximum number in nums. log* is the iterated logarithm, which is a very slowly growing function.

  • The final operation to ensure all elements can reach one another through their factors has a time complexity of O(n) due to the set construction and iteration over the nums array length.

Combining these, the total worst-case time complexity is O(n log*(n) + mx * sqrt(mx)).

Space Complexity

The space complexity of the code can be analyzed as follows:

  • The UnionFind class uses two arrays p and size of length n, giving a space complexity of O(n), where n is the number of elements in the nums array plus the maximum number in nums.

  • The dictionary p in the global scope will have O(mx) keys where mx is the value of 100010. The space complexity for storing lists of factors for each number x is variable, but each list of prime factors has at most O(log x) elements because a number can have at most O(log x) distinct prime factors. This gives a total worst-case space complexity of O(mx log mx).

  • The set used to determine if all indices can be reached from one another in canTraverseAllPairs will contain at most n elements, giving O(n). This might be smaller, but we use the upper bound.

Therefore, the total space complexity is O(n + mx log mx).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Recommended Readings

DSU/Union Find Fundamentals

Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫