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 <= 1051 <= nums[i] <= 105In #2709 Greatest Common Divisor Traversal, the goal is to determine whether all indices of the array can be connected through swaps where the gcd(nums[i], nums[j]) > 1. Instead of checking every pair (which would be too slow), the key insight is to treat numbers as nodes in a graph and connect them if they share a common prime factor.
A practical strategy is to use a Union-Find (Disjoint Set) structure. For each number, compute its prime factors and union the index with other numbers sharing the same factor. A hash map or factor-to-index mapping helps efficiently connect elements that share factors greater than 1. After processing all numbers, check whether all indices belong to the same connected component.
This approach avoids quadratic comparisons and leverages number theory for factorization. With optimized factorization and union operations, the overall complexity is roughly O(n log A) where A is the maximum value in the array.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Union-Find with Prime Factorization | O(n log A) | O(n + A) |
| Naive Pairwise GCD Graph | O(n^2 log A) | O(n^2) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Create a (prime) factor-numbers list for all the indices.
Add an edge between the neighbors of the (prime) factor-numbers list. The order of the numbers doesn’t matter. We only need edges between 2 neighbors instead of edges for all pairs.
The problem is now similar to checking if all the numbers (nodes of the graph) are in the same connected component.
Any algorithm (i.e., BFS, DFS, or Union-Find Set) should work to find or check connected components
This approach considers the integer array as a graph where each index is a node. We connect nodes i and j if gcd(nums[i], nums[j]) > 1. Using a union-find data structure, we efficiently manage connected components as we establish connections among indices. The goal is to determine whether all indices are part of a single connected component.
The time complexity is O(n^2 * log*(n)), due to the nested for loops for each pair of numbers, where log* is the inverse Ackermann function that represents the amortized time of the union-find operations. The space complexity is O(n) for storing the union-find array.
1#include <stdio.h>
2#include <stdlib.h>
3
4int find(int* parents, int x) {
5 if (
This C code uses the union-find algorithm to determine the connectivity of an array. We initialize unconnected components for each element, then iterate through the elements, connecting them if their GCD is greater than 1. If all elements share the same root parent after processing, they belong to a single connected component, implying that traversal is possible between every index.
In this approach, the solution represents the integer array as an adjacency list graph. Each index is considered as a node, and we link them with edges if their GCD is greater than 1. We perform a depth-first search (DFS) or breadth-first search (BFS) to determine the connectivity of the nodes. If all indices are reachable from any starting index, the traversal is possible.
The time complexity is O(n^2), and the space complexity also is O(n^2) due to the adjacency matrix representation.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Union Find helps group indices that are connected through shared factors. Instead of explicitly building a full graph of pairwise GCD relationships, it efficiently merges components whenever two numbers share a prime factor.
Yes, problems combining Union-Find with number theory concepts appear in FAANG-style interviews. This question tests understanding of graph connectivity, prime factorization, and optimization beyond brute-force GCD checks.
The optimal approach uses a Union-Find (Disjoint Set) structure combined with prime factorization. By connecting numbers that share common prime factors greater than 1, we can efficiently determine whether all elements belong to a single connected component.
A Disjoint Set Union (Union-Find) data structure is the most effective. It works well with a hash map or factor mapping that tracks which indices share the same prime factors.
This C code constructs a graph using an adjacency matrix. It uses DFS to check connectivity from the first index to all others, ensuring all indices are reachable.