Tree of Coprimes

Challenge Points: 30

Level: Hard

You are given:

• An integer array values, where values[i] is the number stored at node i.
• A 2-D array links, where each pair [a, b] shows an edge between nodes a and b.

The graph is a tree (connected, no cycles) with node 0 as the root.
Goal
For every node i, find the closest ancestor whose value is coprime with values[i].
Two numbers are coprime if their greatest common divisor (gcd) is 1.
If no such ancestor exists, return -1 for that node.
Return an array answer of size n, where answer[i] is the node number of that closest coprime ancestor, or -1 if none exists.

Example 1:

Input: values = [4, 7, 9, 6] links = [[0,1],[1,2],[1,3]]

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

Explanation:

Node 0: No ancestors → -1 Node 1: Ancestor 0 has value 4 → gcd(7,4)=1 → closest = 0 Node 2: Ancestors 1(7) and 0(4) → gcd(9,7)=1 → closest = 1 Node 3: Ancestors 1(7) and 0(4) → gcd(6,7)=1 → closest = 1

Example 2:

Input: values = [10, 5, 8, 7, 3, 12] links = [[0,1],[0,2],[1,3],[1,4],[2,5]]

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

Explanation:

Node 0: No ancestors → -1 Node 1: Ancestor 0 → gcd(5,10)=5 (not 1)? Wait, gcd(5,10)=5. But only ancestor 0. Actually we need gcd(5,10)=5 not 1. So we must re-check. Let’s adjust numbers so they fit the coprime rule better. Use values = [11, 5, 8, 7, 3, 12] instead (root is 11). Then: Node 1: gcd(5,11)=1 → 0 Node 2: gcd(8,11)=1 → 0 Node 3: gcd(7,5)=1 → 1 Node 4: gcd(3,5)=1 → 1 Node 5: gcd(12,8)=4 (not 1), check 0 → gcd(12,11)=1 → 0

to Continue

Accepted:

Submission:

Report an issue

Code

You need toto run or submitYou need toto run or submit

Test Case

Test Result