There is a tree (i.e., a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. Each node has a value associated with it, and the root of the tree is node 0.
To represent this tree, you are given an integer array nums and a 2D array edges. Each nums[i] represents the ith node's value, and each edges[j] = [uj, vj] represents an edge between nodes uj and vj in the tree.
Two values x and y are coprime if gcd(x, y) == 1 where gcd(x, y) is the greatest common divisor of x and y.
An ancestor of a node i is any other node on the shortest path from node i to the root. A node is not considered an ancestor of itself.
Return an array ans of size n, where ans[i] is the closest ancestor to node i such that nums[i] and nums[ans[i]] are coprime, or -1 if there is no such ancestor.
Example 1:
Input: nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]] Output: [-1,0,0,1] Explanation: In the above figure, each node's value is in parentheses. - Node 0 has no coprime ancestors. - Node 1 has only one ancestor, node 0. Their values are coprime (gcd(2,3) == 1). - Node 2 has two ancestors, nodes 1 and 0. Node 1's value is not coprime (gcd(3,3) == 3), but node 0's value is (gcd(2,3) == 1), so node 0 is the closest valid ancestor. - Node 3 has two ancestors, nodes 1 and 0. It is coprime with node 1 (gcd(3,2) == 1), so node 1 is its closest valid ancestor.
Example 2:
Input: nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]] Output: [-1,0,-1,0,0,0,-1]
Constraints:
nums.length == n1 <= nums[i] <= 501 <= n <= 105edges.length == n - 1edges[j].length == 20 <= uj, vj < nuj != vjThe key idea in #1766 Tree of Coprimes is to traverse the tree while tracking ancestors whose values are coprime with the current node. Since node values are limited (1–50), we can precompute which numbers are coprime using gcd or a lookup table. During a Depth-First Search (DFS), maintain a structure that stores the most recent ancestor index and depth for each value.
When visiting a node, check all possible values (1–50) that are coprime with the current node’s value. Among the stored ancestors with those values, choose the one with the greatest depth as the answer for that node. After processing the node, temporarily record it in the structure and continue DFS to its children, then backtrack when returning.
This approach leverages the small value range to avoid scanning all ancestors, keeping operations efficient. The algorithm runs in roughly O(n × 50) time with O(n + 50) space for DFS tracking and auxiliary structures.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS with coprime value tracking | O(n × 50) | O(n + 50) |
| Precomputing coprime pairs | O(50²) | O(50²) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Note that for a node, it's not optimal to consider two nodes with the same value.
Note that the values are small enough for you to iterate over them instead of iterating over the parent nodes.
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
Problems like Tree of Coprimes reflect patterns commonly tested in FAANG interviews, especially involving DFS, tree traversal, and number theory. While the exact problem may vary, similar concepts appear frequently.
The optimal approach uses Depth-First Search while tracking ancestors by their values. Because node values range from 1 to 50, you can check coprime candidates efficiently using a precomputed table and select the deepest valid ancestor.
The constraint that node values lie between 1 and 50 allows optimization. Instead of checking all ancestors, you only check a fixed set of possible values, which keeps the algorithm near linear time.
A combination of adjacency lists for the tree and arrays or stacks to track the latest ancestor for each value works best. This allows constant-time updates and efficient lookups during DFS traversal.