Tree of Coprimes
01 · Problem
You are given a tree with n nodes labelled 0 to n - 1, rooted at node 0. Node i holds the value nums[i], and edges[j] = [u_j, v_j] is an undirected edge between u_j and v_j.
Two values x and y are coprime when gcd(x, y) == 1. An ancestor of node i is any node on the path from i up to the root, not including i itself.
Return an array ans of length n where ans[i] is the label of the closest ancestor of node i (the one with the greatest depth) whose value is coprime with nums[i], or -1 if no ancestor qualifies.
02 · Examples
nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
[-1,0,0,1]
Node 0 has no ancestors. Nodes 1 and 2 (value 3) are coprime with node 0 (value 2); node 2 skips node 1 because gcd(3, 3) = 3. Node 3 (value 2) is coprime with its parent node 1 (value 3).
nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
[-1,0,-1,0,0,0,-1]
Node 2 (value 10) shares a factor with its only ancestor 5. Node 3 (value 2) shares a factor with 6 but is coprime with 5, so its answer is node 0. Node 6 (value 15) shares a factor with both 10 and 5, so it has no answer.
03 · Constraints
- 01nums.length == n
- 021 <= n <= 105
- 031 <= nums[i] <= 50
- 04edges.length == n - 1 and the edges form a valid tree.
- 050 <= u_j, v_j < n and u_j != v_j
04 · Optimal complexity
- Time
- O(n * V)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.