Greatest Common Divisor Traversal

Greatest Common Divisor Traversal

What is this problem about?

The Greatest Common Divisor Traversal coding problem gives you an array of integers. You can move between index i and index j if and only if the greatest common divisor of nums[i] and nums[j] is strictly greater than 1 (meaning they share a prime factor). You need to determine if you can traverse between all pairs of indices in the array.

Why is this asked in interviews?

This is a "Hard" problem asked by Google. It tests your mastery of the Union Find (Disjoint Set) data structure combined with Number Theory (Prime Factorization). Trying to compute the GCD for every pair of numbers takes $O(N^2)$, which is too slow. It evaluates your ability to use a middleman (the prime factors) to connect indices in $O(N \log (\max(nums)))$ time.

Algorithmic pattern used

This problem uses Union Find with Prime Factor Nodes.

1. Create a Disjoint Set Union (DSU) structure. The nodes will be the array indices AND the prime numbers themselves.
2. For each number nums[i], find its prime factors.
3. For each prime factor p, perform a union operation between the index i and the prime factor p. This means if nums[i] and nums[j] both share prime factor p, they will end up in the same component.
4. Finally, check if all array indices belong to the exact same connected component.

Example explanation

nums = [2, 3, 6]

1. Index 0 (val 2): Primes = {2}. Union(Index 0, Prime 2).
2. Index 1 (val 3): Primes = {3}. Union(Index 1, Prime 3).
3. Index 2 (val 6): Primes = {2, 3}. Union(Index 2, Prime 2), Union(Index 2, Prime 3).
4. Because Index 2 connects to both Prime 2 and Prime 3, it acts as a bridge. Now Index 0 and Index 1 are in the same component. Result: True.

Common mistakes candidates make

• $O(N^2)$ Pairwise Check: Looping through every (i, j) pair and checking gcd(nums[i], nums[j]) > 1.
• Factorizing naively: Not using a precomputed sieve or efficient trial division up to $\sqrt{N}$ to find prime factors.
• Handling 1s: The number 1 has no prime factors. If the array has a 1 and the array length is $> 1$, traversal is immediately impossible because 1 cannot connect to anything.

Interview preparation tip

In graph problems where connectivity is based on a mathematical property (like common factors), treat the mathematical properties (the primes) as actual nodes in your graph.