#1766

Hard

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Tree of Coprimes

Determine the closest coprime ancestor for each node in a tree using efficient traversal and state tracking of node values.

array math tree depth first search number theory

Problem Statement

You are given a tree with n nodes labeled from 0 to n-1, rooted at node 0. Each node has an integer value provided in the array nums, and the tree edges are given as a list of pairs in edges. Your task is to find, for every node, the nearest ancestor node whose value is coprime with the current node's value. If no such ancestor exists, return -1 for that node.

Two integers x and y are considered coprime if gcd(x, y) == 1. Implement an efficient algorithm that avoids redundant comparisons of the same values and correctly handles the tree structure represented by the nums array and edges list, returning an array where each element is the index of the closest coprime ancestor for the corresponding node.

Examples

Example 1

Input: nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]

Output: [-1,0,0,1]

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]

Example details omitted.

Constraints

nums.length == n
1 <= nums[i] <= 50
1 <= n <= 105
edges.length == n - 1
edges[j].length == 2
0 <= uj, vj < n
uj != vj

Solution Approach

Depth-First Search with Ancestor Tracking

Perform DFS from the root, carrying a map from each value to its latest node index in the current path. At each node, iterate over existing keys in the map and compute gcd to find coprime ancestors efficiently.

Use a Stack or Recursive Path Map

Maintain a stack of value-to-node pairs or recursive path map to avoid repeated scanning. Push the current node value when entering and pop when exiting to preserve the correct ancestor mapping for other branches.

Optimize with Value-Based Indexing

Because node values are limited (1-50), precompute coprime pairs to reduce runtime. This prevents repeatedly computing gcd for common values and leverages the constraint to maintain a fast lookup for closest valid ancestors.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * V) where V is the number of unique values (≤50), due to iterating over potential coprime ancestors at each node. Space complexity is O(n + V) to store the tree structure, recursion stack, and value-to-node maps.

What Interviewers Usually Probe

Expect an efficient solution that avoids recomputing gcd repeatedly for same values.
Check whether candidate ancestors are updated correctly on DFS exit to maintain path accuracy.
Confirm that all edge cases with repeated values and root-only coprime scenarios are handled.

Common Pitfalls or Variants

Common pitfalls

Not restoring ancestor mappings after returning from DFS recursion leads to incorrect ancestor assignments.
Failing to precompute or cache coprime relationships causes TLE on large trees.
Assuming nearest coprime ancestor is always immediate parent, ignoring higher ancestors in path.

Follow-up variants

Modify the problem to return all coprime ancestors for each node instead of only the nearest.
Allow dynamic updates to node values and query closest coprime ancestors after each update.
Limit node values to prime numbers and observe how coprime checks simplify.

FAQ

What is the main challenge in Tree of Coprimes?

The challenge is finding the closest coprime ancestor for each node efficiently, especially when values repeat in the tree.

How do you optimize coprime checks in this problem?

Precompute a coprime table for all values 1-50 and use a mapping of values to their latest node index to avoid repeated gcd calculations.

Can this problem be solved iteratively?

Yes, by using an explicit stack to simulate DFS and maintaining a value-to-node map along the current path.

Why can't we just check the parent node for coprimality?

Because the nearest coprime ancestor might be higher up in the tree, not just the immediate parent, so the full path must be considered.

Is memoization useful in Tree of Coprimes?

Yes, caching coprime relationships between values prevents redundant gcd computations and speeds up ancestor searches.

terminal

Solution

Solution 1: Preprocessing + Enumeration + Stack + Backtracking

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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

class Solution:
    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:
        def dfs(i, fa, depth):
            t = k = -1
            for v in f[nums[i]]:
                stk = stks[v]
                if stk and stk[-1][1] > k:
                    t, k = stk[-1]
            ans[i] = t
            for j in g[i]:
                if j != fa:
                    stks[nums[i]].append((i, depth))
                    dfs(j, i, depth + 1)
                    stks[nums[i]].pop()

        g = defaultdict(list)
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)
        f = defaultdict(list)
        for i in range(1, 51):
            for j in range(1, 51):
                if gcd(i, j) == 1:
                    f[i].append(j)
        stks = defaultdict(list)
        ans = [-1] * len(nums)
        dfs(0, -1, 0)
        return ans

Continue Practicing

#2440 create components with same value #1735 count ways to make array with product #1799 maximize score after n operations