In the Tree of Coprimes problem, you are given a rooted tree with n nodes, where each node i (0-indexed) has an integer value nums[i]. The tree is described by a list of edges, and the root is always node 0.
For each node i, you need to find the nearest ancestor of node i (excluding itself) such that the value at that ancestor is coprime with nums[i]. Two numbers are coprime if their greatest common divisor (gcd) is 1. If there is no such ancestor, return -1 for that node.
The output should be an array res of length n, where res[i] is the index of the nearest ancestor of node i whose value is coprime with nums[i], or -1 if none exists.
nums are positive integers (typically ≤ 50 for this problem).The straightforward approach is, for each node, to walk up its ancestry and check the gcd of its value with each ancestor’s value. This is a brute-force solution and can be very slow, especially if the tree is deep and the number of nodes is large.
To optimize, we can traverse the tree in a depth-first search (DFS) manner, keeping track of the most recent occurrence of each value along the path from the root to the current node. Since values are small (usually ≤ 50), we can use a map or array to quickly find the nearest ancestor with a value coprime to the current node’s value.
The key insight is to maintain, for each possible value, the latest node (and its depth) encountered so far in the current path. This allows us to efficiently check all potential coprime ancestors in O(1) per value.
This approach is efficient because it leverages the small range of possible values and avoids redundant computations by using DFS and precomputation.
Sample Input:
nums = [2, 3, 3, 2]edges = [[0,1], [1,2], [1,3]]Tree structure:
0(2)
|
1(3)
/ \
2(3) 3(2)
Step-by-step:
-1.gcd(3,2)=1 (coprime), so result is 0.0.
1.
Final output: [-1, 0, 0, 1]
The Tree of Coprimes problem is an elegant application of DFS with path tracking and precomputation. By leveraging the small value range and using a map to track the most recent occurrence of each value along the current path, we can efficiently find the nearest coprime ancestor for each node. This approach is much faster than brute-force and demonstrates how precomputation and careful state management during DFS can lead to optimal solutions for tree problems with value constraints.
from math import gcd
from collections import defaultdict
class Solution:
def getCoprimes(self, nums, edges):
n = len(nums)
# Build tree
tree = [[] for _ in range(n)]
for u, v in edges:
tree[u].append(v)
tree[v].append(u)
# Precompute coprime pairs
MAXV = 50
coprime = [[] for _ in range(MAXV + 1)]
for i in range(1, MAXV + 1):
for j in range(1, MAXV + 1):
if gcd(i, j) == 1:
coprime[i].append(j)
res = [-1] * n
# For each value, maintain (node, depth)
last_seen = {}
def dfs(u, parent, depth):
# Find nearest ancestor with coprime value
max_depth = -1
ancestor = -1
for val in coprime[nums[u]]:
if val in last_seen:
anc_node, anc_depth = last_seen[val]
if anc_depth > max_depth:
max_depth = anc_depth
ancestor = anc_node
res[u] = ancestor
# Save current state and update
prev = last_seen.get(nums[u], None)
last_seen[nums[u]] = (u, depth)
for v in tree[u]:
if v != parent:
dfs(v, u, depth + 1)
# Restore state
if prev is not None:
last_seen[nums[u]] = prev
else:
del last_seen[nums[u]]
dfs(0, -1, 0)
return res
#include <vector>
#include <algorithm>
#include <numeric>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {
int n = nums.size();
vector<vector<int>> tree(n);
for (auto& e : edges) {
tree[e[0]].push_back(e[1]);
tree[e[1]].push_back(e[0]);
}
// Precompute coprime pairs
const int MAXV = 50;
vector<vector<int>> coprime(MAXV + 1);
for (int i = 1; i <= MAXV; ++i) {
for (int j = 1; j <= MAXV; ++j) {
if (gcd(i, j) == 1)
coprime[i].push_back(j);
}
}
vector<int> res(n, -1);
unordered_map<int, pair<int, int>> last_seen; // value -> (node, depth)
function<void(int, int, int)> dfs = [&](int u, int parent, int depth) {
int max_depth = -1, ancestor = -1;
for (int val : coprime[nums[u]]) {
if (last_seen.count(val)) {
auto [anc_node, anc_depth] = last_seen[val];
if (anc_depth > max_depth) {
max_depth = anc_depth;
ancestor = anc_node;
}
}
}
res[u] = ancestor;
auto prev = last_seen.count(nums[u]) ? make_optional(last_seen[nums[u]]) : nullopt;
last_seen[nums[u]] = {u, depth};
for (int v : tree[u]) {
if (v != parent)
dfs(v, u, depth + 1);
}
if (prev)
last_seen[nums[u]] = *prev;
else
last_seen.erase(nums[u]);
};
dfs(0, -1, 0);
return res;
}
};
import java.util.*;
class Solution {
public int[] getCoprimes(int[] nums, int[][] edges) {
int n = nums.length;
List<List<Integer>> tree = new ArrayList<>();
for (int i = 0; i < n; ++i) tree.add(new ArrayList<>());
for (int[] e : edges) {
tree.get(e[0]).add(e[1]);
tree.get(e[1]).add(e[0]);
}
// Precompute coprime pairs
int MAXV = 50;
List<Integer>[] coprime = new ArrayList[MAXV + 1];
for (int i = 1; i <= MAXV; ++i) {
coprime[i] = new ArrayList<>();
for (int j = 1; j <= MAXV; ++j) {
if (gcd(i, j) == 1)
coprime[i].add(j);
}
}
int[] res = new int[n];
Arrays.fill(res, -1);
Map<Integer, int[]> lastSeen = new HashMap<>(); // value -> [node, depth]
dfs(0, -1, 0, nums, tree, coprime, lastSeen, res);
return res;
}
private void dfs(int u, int parent, int depth, int[] nums, List<List<Integer>> tree,
List<Integer>[] coprime, Map<Integer, int[]> lastSeen, int[] res) {
int maxDepth = -1, ancestor = -1;
for (int val : coprime[nums[u]]) {
if (lastSeen.containsKey(val)) {
int[] anc = lastSeen.get(val);
if (anc[1] > maxDepth) {
maxDepth = anc[1];
ancestor = anc[0];
}
}
}
res[u] = ancestor;
int[] prev = lastSeen.get(nums[u]);
lastSeen.put(nums[u], new int[]{u, depth});
for (int v : tree.get(u)) {
if (v != parent)
dfs(v, u, depth + 1, nums, tree, coprime, lastSeen, res);
}
if (prev != null)
lastSeen.put(nums[u], prev);
else
lastSeen.remove(nums[u]);
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
var getCoprimes = function(nums, edges) {
const n = nums.length;
const tree = Array.from({length: n}, () => []);
for (const [u, v] of edges) {
tree[u].push(v);
tree[v].push(u);
}
// Precompute coprime pairs
const MAXV = 50;
const coprime = Array.from({length: MAXV + 1}, () => []);
for (let i = 1; i <= MAXV; ++i) {
for (let j = 1; j <= MAXV; ++j) {
if (gcd(i, j) === 1) coprime[i].push(j);
}
}
const res = Array(n).fill(-1);
const lastSeen = new Map(); // value -> [node, depth]
function dfs(u, parent, depth) {
let maxDepth = -1, ancestor = -1;
for (const val of coprime[nums[u]]) {
if (lastSeen.has(val)) {
const [ancNode, ancDepth] = lastSeen.get(val);
if (ancDepth > maxDepth) {
maxDepth = ancDepth;
ancestor = ancNode;
}
}
}
res[u] = ancestor;
const prev = lastSeen.has(nums[u]) ? lastSeen.get(nums[u]) : null;
lastSeen.set(nums[u], [u, depth]);
for (const v of tree[u]) {
if (v !== parent) dfs(v, u, depth + 1);
}
if (prev !== null) lastSeen.set(nums[u], prev);
else lastSeen.delete(nums[u]);
}
function gcd(a, b) {
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}
dfs(0, -1, 0);
return res;
};