Tree of Coprimes solution and explanation
Google
6 more videos on this problem
LeetCode 1766. Tree of Coprimes | Biweekly Contest 46 | Hard | Algorithm Explained | C++Cherry Coding [IIT-G] · 23:02 · 1K views
LeetCode 1766. Tree of CoprimesHappy Coding · 23:01 · 1K views
【每日一题】1766. Tree of Coprimes, 2/23/2021Huifeng Guan · 21:31 · 436 views
1766. Tree of Coprimes (Leetcode Hard)Programming Live with Larry · 32:57 · 323 views
LeetCode 1766. Tree of Coprimes宰相小甘罗 · 8:41 · 211 views
Leetcode 1766. Tree of CoprimesFearless Learner · 8:43 · 116 views
LeetCode 1766. Tree of Coprimes 中文宰相小甘罗 · 8:29 · 115 views
The problem
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 != vj
Approach overview
Problem 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 1: Approach 1: Depth-First Search with GCD Check
This method utilizes a depth-first search (DFS) algorithm to traverse the tree. For each node, we check its ancestors to find the closest ancestor that is coprime with the current node. We make use of a stack to backtrack when necessary and a map to keep track of potential coprime ancestors.
from collections import defaultdict
import math
def getCoprimeAncestors(nums, edges):
tree = defaultdict(list)
for u, v in edges:
tree[u].append(v)
tree[v].append(u)
n = len(nums)
ans = [-1] * n
coprimes = [-1] * 51
def dfs(node, parent, depth):
closest = -1
for i in range(1, 51):
if coprimes[i] != -1 and math.gcd(i, nums[node]) == 1:
if closest == -1 or ans[closest] < ans[coprimes[i]]:
closest = coprimes[i]
ans[node] = -1 if closest == -1 else closest
prev_value = coprimes[nums[node]]
coprimes[nums[node]] = node
for child in tree[node]:
if child != parent:
dfs(child, node, depth + 1)
coprimes[nums[node]] = prev_value
dfs(0, -1, 0)
return ans
# Example usage
nums = [5, 6, 10, 2, 3, 6, 15]
edges = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]
print(getCoprimeAncestors(nums, edges))import java.util.*;
class Solution {
public int[] getCoprimeAncestors(int[] nums, int[][] edges) {
int n = nums.length;
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
graph.putIfAbsent(edge[0], new ArrayList<>());
graph.putIfAbsent(edge[1], new ArrayList<>());
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
int[] ans = new int[n];
Arrays.fill(ans, -1);
int[] coprimes = new int[51];
Arrays.fill(coprimes, -1);
dfs(0, -1, 0, coprimes, ans, nums, graph);
return ans;
}
private void dfs(int currentNode, int parent, int depth, int[] coprimes, int[] ans, int[] nums, Map<Integer, List<Integer>> graph) {
int closest = -1;
for (int i = 1; i <= 50; i++) {
if (coprimes[i] != -1 && gcd(i, nums[currentNode]) == 1) {
if (closest == -1 || ans[closest] < ans[coprimes[i]]) {
closest = coprimes[i];
}
}
}
ans[currentNode] = (closest == -1) ? -1 : ans[closest];
int prevValue = coprimes[nums[currentNode]];
coprimes[nums[currentNode]] = currentNode;
for (int neighbor : graph.getOrDefault(currentNode, new ArrayList<>())) {
if (neighbor != parent) {
dfs(neighbor, currentNode, depth + 1, coprimes, ans, nums, graph);
}
}
coprimes[nums[currentNode]] = prevValue; // backtrack
}
private int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {5, 6, 10, 2, 3, 6, 15};
int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}};
System.out.println(Arrays.toString(sol.getCoprimeAncestors(nums, edges)));
}
}#include <vector>
#include <numeric>
using namespace std;
class Solution {
public:
void dfs(vector<vector<int>>& tree, vector<int>& nums, vector<int>& ans, int node, vector<int>& coprimes, vector<int>& depths, int depth) {
int closest = -1;
for (int i = 1; i <= 50; ++i) {
if (coprimes[i] != -1 && gcd(i, nums[node]) == 1 && (closest == -1 || depths[coprimes[i]] > depths[closest])) {
closest = coprimes[i];
}
}
ans[node] = closest;
int prev = coprimes[nums[node]];
coprimes[nums[node]] = node;
depths[node] = depth;
for (int &neighbor : tree[node]) {
if (ans[neighbor] == -2) { // not visited
dfs(tree, nums, ans, neighbor, coprimes, depths, depth+1);
}
}
coprimes[nums[node]] = prev;
}
vector<int> getCoprimeAncestors(vector<int>& nums, vector<vector<int>>& edges) {
int n = nums.size();
vector<vector<int>> tree(n);
for (auto& edge : edges) {
tree[edge[0]].push_back(edge[1]);
tree[edge[1]].push_back(edge[0]);
}
vector<int> ans(n, -2);
vector<int> coprimes(51, -1);
vector<int> depths(n, -1);
dfs(tree, nums, ans, 0, coprimes, depths, 0);
return ans;
}
};
// Example Usage
#include<iostream>
int main() {
Solution sol;
vector<int> nums = {5, 6, 10, 2, 3, 6, 15};
vector<vector<int>> edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}};
vector<int> result = sol.getCoprimeAncestors(nums, edges);
cout << "[";
for (int i = 0; i < result.size(); ++i) {
cout << result[i];
if (i < result.size() - 1) cout << ", ";
}
cout << "]" << endl;
return 0;
}function gcd(x, y) {
while (y !== 0) {
let temp = y;
y = x % y;
x = temp;
}
return x;
}
function getCoprimeAncestors(nums, edges) {
let n = nums.length;
let graph = Array.from({length: n}, () => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
let ans = Array(n).fill(-1);
let coprimes = Array(51).fill(-1);
function dfs(node, parent, depth) {
let closest = -1;
for (let i = 1; i <= 50; i++) {
if (coprimes[i] !== -1 && gcd(i, nums[node]) === 1) {
if (closest === -1 || ans[closest] < ans[coprimes[i]]) {
closest = coprimes[i];
}
}
}
ans[node] = closest;
const prev = coprimes[nums[node]];
coprimes[nums[node]] = node;
for (const neighbor of graph[node]) {
if (neighbor !== parent) {
dfs(neighbor, node, depth + 1);
}
}
coprimes[nums[node]] = prev;
}
dfs(0, -1, 0);
return ans;
}
// Example Usage
elements = [5, 6, 10, 2, 3, 6, 15];
edgesElements = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]];
console.log(getCoprimeAncestors(elements, edgesElements));#include <stdio.h>
#include <stdlib.h>
// Structure to represent a node in the adjacency list
struct Node {
int vertex;
struct Node* next;
};
// Structure to represent the adjacency list
struct Graph {
int numVertices;
struct Node** adjLists;
};
// Function to create a graph
struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = (struct Node**)malloc(vertices * sizeof(struct Node*));
for (int i = 0; i < vertices; i++)
graph->adjLists[i] = NULL;
return graph;
}
// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->vertex = dest;
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->vertex = src;
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
void dfs(struct Graph* graph, int* nums, int current, int parent, int* ans, int* coprime_ancestors) {
int nodeValue = nums[current];
int closestAncestor = -1;
for (int i = 0; i < 51; i++) {
if (coprime_ancestors[i] != -1 && gcd(i, nodeValue) == 1) {
if (closestAncestor == -1 || coprime_ancestors[i] > ans[closestAncestor]) {
closestAncestor = coprime_ancestors[i];
}
}
}
ans[current] = closestAncestor;
int prevAncestor = coprime_ancestors[nodeValue];
coprime_ancestors[nodeValue] = current;
struct Node* temp = graph->adjLists[current];
while (temp) {
if (temp->vertex != parent) {
dfs(graph, nums, temp->vertex, current, ans, coprime_ancestors);
}
temp = temp->next;
}
coprime_ancestors[nodeValue] = prevAncestor;
}
int* getCoprimeAncestors(int* nums, int numsSize, int** edges, int edgesSize, int* returnSize) {
struct Graph* graph = createGraph(numsSize);
for (int i = 0; i < edgesSize; i++) {
addEdge(graph, edges[i][0], edges[i][1]);
}
int* ans = (int*)malloc(numsSize * sizeof(int));
int coprime_ancestors[51];
for (int i = 0; i < 51; i++)
coprime_ancestors[i] = -1;
dfs(graph, nums, 0, -1, ans, coprime_ancestors);
*returnSize = numsSize;
return ans;
}
int main() {
int nums[] = {5, 6, 10, 2, 3, 6, 15};
int numEdges = 6;
int edges[6][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}};
int* edgesPointers[6];
for (int i = 0; i < numEdges; ++i) {
edgesPointers[i] = edges[i];
}
int returnSize;
int* result = getCoprimeAncestors(nums, 7, edgesPointers, numEdges, &returnSize);
printf("[ ");
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
printf("]\n");
return 0;
}using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public int[] GetCoprimeAncestors(int[] nums, int[][] edges) {
int n = nums.Length;
List<int>[] tree = new List<int>[n];
for (int i = 0; i < n; i++) {
tree[i] = new List<int>();
}
foreach (var edge in edges) {
tree[edge[0]].Add(edge[1]);
tree[edge[1]].Add(edge[0]);
}
int[] ans = new int[n];
Array.Fill(ans, -1);
int[] coprimes = new int[51];
Array.Fill(coprimes, -1);
int[] depths = new int[n];
dfs(0, -1, 0, coprimes, levels, nums, tree, ans);
return ans;
}
private void dfs(int node, int parent, int depth, int[] coprimes, int[] depths, int[] nums, List<int>[] tree, int[] ans) {
int closest = -1;
for (int i = 1; i <= 50; i++) {
if (coprimes[i] != -1 && GCD(i, nums[node]) == 1) {
if (closest == -1 || depths[coprimes[i]] > depths[closest]) {
closest = coprimes[i];
}
}
}
ans[node] = closest;
int previousCoprime = coprimes[nums[node]];
coprimes[nums[node]] = node;
depths[node] = depth;
foreach (var neighbor in tree[node]) {
if (neighbor != parent) {
dfs(neighbor, node, depth + 1, coprimes, depths, nums, tree, ans);
}
}
coprimes[nums[node]] = previousCoprime;
}
private int GCD(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = { 5, 6, 10, 2, 3, 6, 15 };
int[][] edges = new int[][] {
new int[] { 0, 1 },
new int[] { 0, 2 },
new int[] { 1, 3 },
new int[] { 1, 4 },
new int[] { 2, 5 },
new int[] { 2, 6 }
};
int[] result = sol.GetCoprimeAncestors(nums, edges);
Console.WriteLine("[" + string.Join(", ", result) + "]");
}
}This Python solution constructs the tree as an adjacency list using defaultdict from the collections module. Using DFS, it traverses the nodes recursively and maintains a list of potential coprime ancestors based on previous visitation records. The GCD function from the math module is used to check coprimeness efficiently. This solution explores potential ancestor connections and appropriately backtracks using recursive calls effectively.
Time Complexity: O(n), since each node is visited once during the tree traversal.
Space Complexity: O(n), for recursion depth and auxiliary data structures for the tree.
Approach 2: 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.
Next, we can use a backtracking method to traverse the entire tree from the root node. For each node i, we can get all the coprime numbers of nums[i] through the array f. Then we enumerate all the coprime numbers of nums[i], find the ancestor node t that has appeared and has the maximum depth, which is the nearest coprime ancestor node of i. Here we can use a stack array stks of length 51 to get each appeared value v and its depth. The top element of each stack stks[v] is the nearest ancestor node with the maximum depth.
The time complexity is O(n times M), and the space complexity is O(M^2 + n). Where n is the number of nodes, and M is the maximum value of nums[i], in this problem M = 50.
func getCoprimes(nums []int, edges [][]int) []int {
n := len(nums)
g := make([][]int, n)
f := [51][]int{}
type pair struct{ first, second int }
stks := [51][]pair{}
for _, e := range edges {
u, v := e[0], e[1]
g[u] = append(g[u], v)
g[v] = append(g[v], u)
}
for i := 1; i < 51; i++ {
for j := 1; j < 51; j++ {
if gcd(i, j) == 1 {
f[i] = append(f[i], j)
}
}
}
ans := make([]int, n)
var dfs func(i, fa, depth int)
dfs = func(i, fa, depth int) {
t, k := -1, -1
for _, v := range f[nums[i]] {
stk := stks[v]
if len(stk) > 0 && stk[len(stk)-1].second > k {
t, k = stk[len(stk)-1].first, stk[len(stk)-1].second
}
}
ans[i] = t
for _, j := range g[i] {
if j != fa {
stks[nums[i]] = append(stks[nums[i]], pair{i, depth})
dfs(j, i, depth+1)
stks[nums[i]] = stks[nums[i]][:len(stks[nums[i]])-1]
}
}
}
dfs(0, -1, 0)
return ans
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Depth-First Search with GCD Check | Time Complexity: O(n), since each node is visited once during the tree traversal. |
| Preprocessing + Enumeration + Stack + Backtracking | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Tree of Coprimes easy or hard?
Tree of Coprimes is rated Hard because it combines multiple concepts: tree traversal, ancestor tracking, and number theory with GCD. The key difficulty is avoiding an O(n^2) ancestor search by exploiting the limited value range.
Tree of Coprimes Python/Java solution
Implement a DFS that maintains stacks indexed by node value. Before exploring children, determine the nearest coprime ancestor by scanning stacks of compatible values. The same logic works in Python, Java, C++, and JavaScript with minor syntax differences.
How to solve Tree of Coprimes in O(n)?
Treat the tree traversal as DFS while keeping stacks of ancestors grouped by value. Because node values are limited to 1–50, you only examine values coprime with the current node instead of scanning all ancestors. This limits work per node to a small constant factor, making the algorithm effectively linear.
What is the best approach for Tree of Coprimes?
The most efficient approach uses Depth-First Search with value tracking. Maintain stacks for each value (1–50) representing ancestors on the current DFS path. For every node, check stacks of values that are coprime with its value and choose the deepest ancestor. This reduces the search to at most 50 checks per node.
Is Tree of Coprimes asked at Google/Amazon/Meta?
Tree and number theory problems similar to Tree of Coprimes appear in interviews at companies like Google, Amazon, and Meta. Interviewers often test DFS traversal combined with mathematical constraints such as GCD or coprime checks.
What data structure is used in Tree of Coprimes?
The solution uses an adjacency list for the tree, recursion or a stack for DFS traversal, and 50 auxiliary stacks (or arrays) to track the most recent ancestor for each value. A GCD function from number theory determines whether two values are coprime.
What is the time complexity of Tree of Coprimes?
The optimized DFS solution runs in O(n * 50) time where n is the number of nodes. Each node checks at most 50 possible coprime values. Space complexity is O(n + 50) due to recursion and stacks storing ancestors along the path.