Greatest Common Divisor Traversal

Hard

#2444Time: O(N^2 * log(M)), where N is the length of `nums` and M is the maximum value in `nums`. We iterate through O(N^2) pairs, and for each pair, the GCD calculation takes O(log(M)) time.Space: O(N), where N is the number of elements in `nums`. This space is used for the DSU data structure.

Patterns

Math Number Theory

Algorithms

Union Find

Data structures

Array

Prompt

You are given a 0-indexed integer array nums, and you are allowed to traverse between its indices. You can traverse between index i and index j, i != j, if and only if gcd(nums[i], nums[j]) > 1, where gcd is the greatest common divisor.

Your task is to determine if for every pair of indices i and j in nums, where i < j, there exists a sequence of traversals that can take us from i to j.

Return true if it is possible to traverse between all such pairs of indices, or false otherwise.

Example 1:

Input: nums = [2,3,6]
Output: true
Explanation: In this example, there are 3 possible pairs of indices: (0, 1), (0, 2), and (1, 2).
To go from index 0 to index 1, we can use the sequence of traversals 0 -> 2 -> 1, where we move from index 0 to index 2 because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1, and then move from index 2 to index 1 because gcd(nums[2], nums[1]) = gcd(6, 3) = 3 > 1.
To go from index 0 to index 2, we can just go directly because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1. Likewise, to go from index 1 to index 2, we can just go directly because gcd(nums[1], nums[2]) = gcd(3, 6) = 3 > 1.

Example 2:

Input: nums = [3,9,5]
Output: false
Explanation: No sequence of traversals can take us from index 0 to index 2 in this example. So, we return false.

Example 3:

Input: nums = [4,3,12,8]
Output: true
Explanation: There are 6 possible pairs of indices to traverse between: (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), and (2, 3). A valid sequence of traversals exists for each pair, so we return true.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach treats the problem as a graph connectivity problem. We can determine if all nodes are connected by checking every pair of numbers. If their Greatest Common Divisor (GCD) is greater than 1, they are connected. We can use a Disjoint Set Union (DSU) data structure to efficiently track the connected components. We iterate through all possible pairs of indices, and if their corresponding numbers share a common factor, we merge their sets. Finally, we check if all indices belong to a single component.

Algorithm

The problem can be modeled as a graph problem. Each index of the nums array is a node in the graph.
An edge exists between two nodes (indices) i and j if gcd(nums[i], nums[j]) > 1.
The question is equivalent to checking if this graph is connected.
A straightforward way to check for connectivity is to build the graph and then perform a graph traversal (like DFS or BFS) to see if all nodes can be reached from a single source.
A more direct way that avoids building an explicit adjacency list is to use a Disjoint Set Union (DSU) data structure.
Initialize a DSU structure with N sets, one for each index.
Iterate through every pair of indices (i, j).
If gcd(nums[i], nums[j]) > 1, perform a union operation on the sets containing i and j.
After checking all pairs, if there's only one disjoint set left, it means the graph is fully connected.

Walkthrough

The brute-force approach involves checking every possible pair of numbers in the array. For each pair (nums[i], nums[j]), we calculate their GCD. If the GCD is greater than 1, it means we can traverse between index i and j, so we consider them part of the same connected component.

We use a Disjoint Set Union (DSU) data structure to keep track of these components. Initially, each index is in its own component. When we find a pair (i, j) with gcd(nums[i], nums[j]) > 1, we merge the components of i and j using the union operation.

After iterating through all O(N^2) pairs, we check the number of disjoint sets remaining in our DSU structure. If there is only one set, it means all indices are mutually reachable, and the graph is connected. We return true. Otherwise, we return false.

1class Solution {2    public boolean canTraverseAllPairs(int[] nums) {3        int n = nums.length;4        if (n == 1) {5            return true;6        }7 8        DSU dsu = new DSU(n);9        for (int i = 0; i < n; i++) {10            for (int j = i + 1; j < n; j++) {11                if (gcd(nums[i], nums[j]) > 1) {12                    dsu.union(i, j);13                }14            }15        }16 17        return dsu.getComponents() == 1;18    }19 20    private int gcd(int a, int b) {21        while (b != 0) {22            int temp = b;23            b = a % b;24            a = temp;25        }26        return a;27    }28 29    class DSU {30        int[] parent;31        int components;32 33        public DSU(int n) {34            parent = new int[n];35            components = n;36            for (int i = 0; i < n; i++) {37                parent[i] = i;38            }39        }40 41        public int find(int i) {42            if (parent[i] == i) {43                return i;44            }45            return parent[i] = find(parent[i]);46        }47 48        public void union(int i, int j) {49            int rootI = find(i);50            int rootJ = find(j);51            if (rootI != rootJ) {52                parent[rootJ] = rootI;53                components--;54            }55        }56 57        public int getComponents() {58            return components;59        }60    }61}

Complexity

Time

O(N^2 * log(M)), where N is the length of `nums` and M is the maximum value in `nums`. We iterate through O(N^2) pairs, and for each pair, the GCD calculation takes O(log(M)) time.

Space

O(N), where N is the number of elements in `nums`. This space is used for the DSU data structure.

Trade-offs

Pros

Simple to conceptualize and implement.
Correctly solves the problem for small inputs.

Cons

The time complexity of O(N^2 * log(M)) is too high for the given constraints (N up to 10^5), leading to a 'Time Limit Exceeded' error on larger test cases.

A more efficient approach avoids the O(N^2) pairwise comparisons by focusing on the prime factors of the numbers. The condition gcd(a, b) > 1 is equivalent to a and b sharing at least one common prime factor. This means we can form connected components by linking numbers that share prime factors.

We can use a Disjoint Set Union (DSU) data structure to group indices. For each number in the input array, we find its prime factors. Then, for each prime factor, we union the current number's index with the index of the first number we saw that had this prime factor. This way, all numbers sharing a prime factor will end up in the same component.

To make prime factorization fast, we first pre-compute the smallest prime factor for all numbers up to the maximum value in the input array using a sieve.

Algorithm

The core idea is that two numbers nums[i] and nums[j] are connected if they share a common prime factor.
Instead of checking pairs of numbers, we can connect indices based on their prime factors. If nums[i] and nums[j] both have a prime factor p, they are in the same connected component.
We can use a DSU data structure on the indices of the array.
The overall algorithm is as follows:
1. Handle edge cases: If n=1, return true. If n > 1 and 1 is present in nums, return false because 1 cannot be connected to any other number.
2. Find the maximum value M in nums.
3. Pre-compute the Smallest Prime Factor (SPF) for all numbers up to M using a sieve. This will allow for efficient prime factorization of each number.
4. Initialize a DSU for N indices and a hash map primeToIndex to store the first index encountered for each prime factor.
5. Iterate through each index i from 0 to N-1: a. Get the unique prime factors of nums[i] using the pre-computed SPF array. b. For each prime factor p: i. If primeToIndex already contains p, it means we've seen this prime before at index j = primeToIndex.get(p). We union the sets of i and j. ii. Otherwise, we map this prime p to the current index i in primeToIndex.
6. After iterating through all numbers, check if the DSU has only one component. If so, all pairs are traversable, and we return true.

Walkthrough

This optimized solution leverages number theory to avoid the costly pairwise checks. Here's a step-by-step breakdown:

Edge Cases: A single-element array is trivially connected. If the array has more than one element and contains a 1, it's impossible to connect the index of 1 to any other index, since gcd(1, x) = 1 for all x. So, we handle these cases first.
Sieve for Smallest Prime Factor (SPF): We find the maximum value M in nums. Then, we use a sieve (similar to Sieve of Eratosthenes) to create an spf array of size M+1. spf[k] will store the smallest prime factor of k. This pre-computation takes O(M log log M) time and allows us to find the prime factors of any number x <= M in O(log x) time.
DSU and Prime-to-Index Map: We initialize a DSU structure for N indices. We also use a HashMap<Integer, Integer> called primeToIndex which will map a prime number to the first index i we encounter where nums[i] is divisible by that prime.
Union by Prime Factors: We iterate through nums. For each nums[i], we find its unique prime factors. For each prime factor p, we check our primeToIndex map. If p is already in the map, it means another number nums[j] (where j = primeToIndex.get(p)) shares this prime factor. We then call dsu.union(i, j). If p is not in the map, we add it, mapping it to the current index i.
Final Connectivity Check: After processing all numbers, if all indices have been merged into a single component in the DSU, it means the entire graph is connected. We can check this by seeing if the number of components in the DSU is 1.

1import java.util.*;2 3class Solution {4    public boolean canTraverseAllPairs(int[] nums) {5        int n = nums.length;6        if (n == 1) return true;7 8        int maxVal = 0;9        for (int num : nums) {10            if (num == 1) return false; // If n > 1 and 1 is present, impossible.11            maxVal = Math.max(maxVal, num);12        }13 14        int[] spf = new int[maxVal + 1];15        for (int i = 2; i <= maxVal; i++) {16            spf[i] = i;17        }18        for (int i = 2; i * i <= maxVal; i++) {19            if (spf[i] == i) { // i is a prime number20                for (int j = i * i; j <= maxVal; j += i) {21                    if (spf[j] == j) { // If spf[j] hasn't been set yet22                        spf[j] = i;23                    }24                }25            }26        }27 28        DSU dsu = new DSU(n);29        Map<Integer, Integer> primeToIndex = new HashMap<>();30 31        for (int i = 0; i < n; i++) {32            int num = nums[i];33            while (num > 1) {34                int p = spf[num];35                if (primeToIndex.containsKey(p)) {36                    dsu.union(i, primeToIndex.get(p));37                } else {38                    primeToIndex.put(p, i);39                }40                while (num % p == 0) {41                    num /= p;42                }43            }44        }45 46        return dsu.getComponents() == 1;47    }48 49    class DSU {50        int[] parent;51        int[] size;52        int components;53 54        public DSU(int n) {55            parent = new int[n];56            size = new int[n];57            components = n;58            for (int i = 0; i < n; i++) {59                parent[i] = i;60                size[i] = 1;61            }62        }63 64        public int find(int i) {65            if (parent[i] == i) {66                return i;67            }68            return parent[i] = find(parent[i]);69        }70 71        public void union(int i, int j) {72            int rootI = find(i);73            int rootJ = find(j);74            if (rootI != rootJ) {75                if (size[rootI] < size[rootJ]) {76                    int temp = rootI;77                    rootI = rootJ;78                    rootJ = temp;79                }80                parent[rootJ] = rootI;81                size[rootI] += size[rootJ];82                components--;83            }84        }85 86        public int getComponents() {87            return components;88        }89    }90}

Complexity

Time

O(M * log(log(M)) + N * α(N) * log(M)), where N is `nums.length`, M is `max(nums)`, and α is the Inverse Ackermann function. The sieve takes O(M log log M). The main loop is O(N). Inside, prime factorization takes O(log M) and DSU operations are nearly constant O(α(N)). This simplifies to being dominated by the sieve and the main loop, making it very fast.

Space

O(N + M), where N is the length of `nums` and M is the maximum value. O(N) for the DSU, O(M) for the SPF array, and up to O(π(M)) for the map, where π(M) is the number of primes up to M.

Trade-offs

Pros

Highly efficient, with a time complexity that passes the given constraints.
Scales well for large inputs where N and M are up to 10^5.

Cons

The implementation is more complex, requiring knowledge of number theory concepts like sieves and prime factorization.
It uses more space due to the SPF array and the map, with a complexity of O(N + M).

Solutions

Solution

1class UnionFind { private int [] p ; private int [] size ; public UnionFind ( int n ) { p = new int [ n ]; size = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { p [ i ] = i ; size [ i ] = 1 ; } } public int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } public boolean union ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa == pb ) { return false ; } if ( size [ pa ] > size [ pb ]) { p [ pb ] = pa ; size [ pa ] += size [ pb ]; } else { p [ pa ] = pb ; size [ pb ] += size [ pa ]; } return true ; } } class Solution { private static final int MX = 100010 ; private static final List < Integer >[] P = new List [ MX ]; static { Arrays . setAll ( P , k -> new ArrayList <>()); for ( int x = 1 ; x < MX ; ++ x ) { int v = x ; int i = 2 ; while ( i <= v / i ) { if ( v % i == 0 ) { P [ x ]. add ( i ); while ( v % i == 0 ) { v /= i ; } } ++ i ; } if ( v > 1 ) { P [ x ]. add ( v ); } } } public boolean canTraverseAllPairs ( int [] nums ) { int m = Arrays . stream ( nums ). max (). getAsInt (); int n = nums . length ; UnionFind uf = new UnionFind ( n + m + 1 ); for ( int i = 0 ; i < n ; ++ i ) { for ( int j : P [ nums [ i ]]) { uf . union ( i , j + n ); } } Set < Integer > s = new HashSet <>(); for ( int i = 0 ; i < n ; ++ i ) { s . add ( uf . find ( i )); } return s . size () == 1 ; } }

1int MX = 100010 ; vector < int > P [ 100010 ]; int init = []() { for ( int x = 1 ; x < MX ; ++ x ) { int v = x ; int i = 2 ; while ( i <= v / i ) { if ( v % i == 0 ) { P [ x ]. push_back ( i ); while ( v % i == 0 ) { v /= i ; } } ++ i ; } if ( v > 1 ) { P [ x ]. push_back ( v ); } } return 0 ; }(); class UnionFind { public: UnionFind ( int n ) { p = vector < int > ( n ); size = vector < int > ( n , 1 ); iota ( p . begin (), p . end (), 0 ); } bool unite ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa == pb ) { return false ; } if ( size [ pa ] > size [ pb ]) { p [ pb ] = pa ; size [ pa ] += size [ pb ]; } else { p [ pa ] = pb ; size [ pb ] += size [ pa ]; } return true ; } int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } private: vector < int > p , size ; }; class Solution { public: bool canTraverseAllPairs ( vector < int >& nums ) { int m = * max_element ( nums . begin (), nums . end ()); int n = nums . size (); UnionFind uf ( m + n + 1 ); for ( int i = 0 ; i < n ; ++ i ) { for ( int j : P [ nums [ i ]]) { uf . unite ( i , j + n ); } } unordered_set < int > s ; for ( int i = 0 ; i < n ; ++ i ) { s . insert ( uf . find ( i )); } return s . size () == 1 ; } };

1class UnionFind : def __init__ ( self , n ): self . p = list ( range ( n )) self . size = [ 1 ] * n def find ( self , x ): if self . p [ x ] != x : self . p [ x ] = self . find ( self . p [ x ]) return self . p [ x ] def union ( self , a , b ): pa , pb = self . find ( a ), self . find ( b ) if pa == pb : return False if self . size [ pa ] > self . size [ pb ]: self . p [ pb ] = pa self . size [ pa ] += self . size [ pb ] else : self . p [ pa ] = pb self . size [ pb ] += self . size [ pa ] return True mx = 100010 p = defaultdict ( list ) for x in range ( 1 , mx + 1 ): v = x i = 2 while i <= v // i : if v % i == 0 : p [ x ]. append ( i ) while v % i == 0 : v //= i i += 1 if v > 1 : p [ x ]. append ( v ) class Solution : def canTraverseAllPairs ( self , nums : List [ int ]) -> bool : n = len ( nums ) m = max ( nums ) uf = UnionFind ( n + m + 1 ) for i , x in enumerate ( nums ): for j in p [ x ]: uf . union ( i , j + n ) return len ( set ( uf . find ( i ) for i in range ( n ))) == 1

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem