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 != vjProblem Overview: You are given a tree where each node contains a value. For every node, return the closest ancestor whose value is coprime with the current node's value. If no such ancestor exists, return -1. The challenge is efficiently searching ancestors while traversing the tree.
Approach 1: Brute Force Ancestor Scan (O(n^2) time, O(n) space)
Traverse the tree and, for each node, walk up its ancestor chain until reaching the root. At every step compute gcd(nodeValue, ancestorValue). The first ancestor with gcd == 1 is the answer. This approach relies on parent pointers or storing the current path during a Depth-First Search. The problem is worst‑case complexity: a skewed tree may require scanning up to n ancestors for each node, producing O(n^2) time.
Approach 2: DFS with Coprime Value Tracking (O(n * 50) time, O(n + 50) space)
The optimized solution leverages the constraint that node values are small (1–50). Precompute which values are coprime with each other using gcd from number theory. During a DFS traversal of the tree, maintain an array of stacks indexed by value (1..50). Each stack stores nodes with that value along the current root‑to‑node path along with their depths.
When visiting a node with value v, iterate through all values 1..50 that are coprime with v. For each candidate value, check the most recent node in its stack (the deepest ancestor with that value). Track the ancestor with the maximum depth and record it as the answer. After processing the node, push it onto the stack corresponding to its value, explore children recursively using DFS, then pop it when backtracking.
This technique turns the ancestor search into a constant‑bounded scan over 50 possible values rather than scanning the entire path. Each node performs at most 50 checks, giving O(n * 50) time which behaves like linear time in practice. The extra space comes from recursion plus the value stacks.
Recommended for interviews: The DFS with coprime value tracking is the expected solution. Interviewers want to see two insights: modeling the graph as a DFS traversal and exploiting the small value range (≤50) to avoid scanning the full ancestor path. Mentioning the brute force ancestor scan first shows understanding of the problem before optimizing it.
This method utilizes a depth-first search (DFS) algorithm to traverse the tree. For each node, we check its ancestors to find the closest ancestor that is coprime with the current node. We make use of a stack to backtrack when necessary and a map to keep track of potential coprime ancestors.
This solution uses a DFS recursively over nodes of the tree, passing the current node's value to check against ancestors stored in `coprime_ancestors`. Ancestors' indices are stored for reference if they meet the coprime condition. GCD is computed for all values to determine coprimeness. The complexity is efficiently handled due to the limited scope of values (1-50), allowing constant-time updates and lookups in the array.
Time Complexity: O(n), where n is the number of nodes, as we perform DFS.
Space Complexity: O(n + 50), i.e., O(n) for results and coprime ancestors map.
Since the range of nums[i] in the problem is [1, 50], we can preprocess all the coprime numbers for each number and record them in the array f, where f[i] represents all the coprime numbers of i.
Next, we can use a backtracking method to traverse the entire tree from the root node. For each node i, we can get all the coprime numbers of nums[i] through the array f. Then we enumerate all the coprime numbers of nums[i], find the ancestor node t that has appeared and has the maximum depth, which is the nearest coprime ancestor node of i. Here we can use a stack array stks of length 51 to get each appeared value v and its depth. The top element of each stack stks[v] is the nearest ancestor node with the maximum depth.
The time complexity is O(n times M), and the space complexity is O(M^2 + n). Where n is the number of nodes, and M is the maximum value of nums[i], in this problem M = 50.
| Approach | Complexity |
|---|---|
| Approach 1: Depth-First Search with GCD Check | Time Complexity: O(n), where n is the number of nodes, as we perform DFS. |
| Preprocessing + Enumeration + Stack + Backtracking | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Ancestor Scan with GCD | O(n^2) | O(n) | Conceptual baseline or when constraints are very small |
| DFS with Coprime Value Stacks | O(n * 50) | O(n + 50) | Optimal solution for large trees; leverages limited value range |
LeetCode 1766. Tree of Coprimes | Biweekly Contest 46 | Hard | Algorithm Explained | C++ • Cherry Coding [IIT-G] • 1,350 views views
Watch 6 more video solutions →Practice Tree of Coprimes with our built-in code editor and test cases.
Practice on FleetCode