Watch 7 video solutions for Tree of Coprimes, a hard level problem involving Array, Math, Tree. This walkthrough by Cherry Coding [IIT-G] has 1,350 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |