Greatest Common Divisor Traversal

Greatest Common Divisor Traversal is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Union-Find (Disjoint Set Union - DSU) subpattern.

Problem statement

Implement Solution.canTraverseAllPairs, which receives an integer array nums. Treat each array position as a vertex; positions remain distinct even when their values are equal.

You may move directly between two different positions i and j when gcd(nums[i], nums[j]) is greater than 1, where gcd is the greatest common divisor. A position is reachable from another if there is a sequence of such direct moves, possibly passing through other positions.

Return true exactly when every pair of positions in nums is mutually reachable. Return false otherwise. An array with one position is considered fully reachable.

Example 1:

Input: nums = [14,25,35,77] Output: true Explanation: The values connect through shared prime factors: 14 connects to 35 through 7, 35 connects to 25 through 5, and 35 connects to 77 through 7. Thus every position belongs to one reachable component.

Example 2:

Input: nums = [6,35,77] Output: false Explanation: 35 and 77 share a factor of 7, but 6 shares no factor greater than 1 with either value, so its position is isolated.

Example 3:

Input: nums = [1] Output: true Explanation: There is only one position, so there is no other position that must be reached.

Constraints:

- 1 <= nums.length <= 10^5 - 1 <= nums[i] <= 10^5 - All elements of nums are integers.

Topics and companies

Topics: Union Find, Graph, Number Theory, Array.

How to practise Greatest Common Divisor Traversal on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(M log log M + n log M · α(n + M)), where M is the maximum value in nums; equivalently, factoring and union operations are near-linear in the input size for the given bounds. time and O(n + M) space.

Open Greatest Common Divisor Traversal in the code editor, or read the Greatest Common Divisor Traversal editorial for a worked solution with its approach and complexity analysis.

Where Greatest Common Divisor Traversal sits in the DSA pattern sheet

Problems related to Greatest Common Divisor Traversal

Other problems that use the same Union-Find (Disjoint Set Union - DSU) and Graph Traversal Patterns (DFS & BFS) techniques:

Preparing this workspace.