In this guide, you will get 1766. Tree of Coprimes LeetCode Solution with the best time and space complexity. The solution to Tree of Coprimes problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
nums.length == n
1 <= nums[i] <= 50
1 <= n <= 105
edges.length == n – 1
edges[j].length == 2
0 <= uj, vj < n
uj != vj
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
1766. Tree of Coprimes LeetCode Solution in C++
class Solution {
public:
vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {
vector<int> ans(nums.size(), -1);
vector<vector<int>> tree(nums.size());
// stacks[i] := (node, depth)s of nodes with value i
vector<stack<pair<int, int>>> stacks(kMax + 1);
for (const vector<int> edge : edges) {
const int u = edge[0];
const int v = edge[1];
tree[u].push_back(v);
tree[v].push_back(u);
}
dfs(tree, 0, /*prev=*/-1, /*depth=*/0, nums, stacks, ans);
return ans;
}
private:
static constexpr int kMax = 50;
void dfs(const vector<vector<int>>& tree, int u, int prev, int depth,
const vector<int>& nums, vector<stack<pair<int, int>>>& stacks,
vector<int>& ans) {
ans[u] = getAncestor(u, stacks, nums);
stacks[nums[u]].push({u, depth});
for (const int v : tree[u])
if (v != prev)
dfs(tree, v, u, depth + 1, nums, stacks, ans);
stacks[nums[u]].pop();
}
int getAncestor(int u, const vector<stack<pair<int, int>>>& stacks,
const vector<int>& nums) {
int maxNode = -1;
int maxDepth = -1;
for (int i = 1; i <= kMax; ++i)
if (!stacks[i].empty() && stacks[i].top().second > maxDepth &&
__gcd(nums[u], i) == 1) {
maxNode = stacks[i].top().first;
maxDepth = stacks[i].top().second;
}
return maxNode;
}
}; /* code provided by PROGIEZ */
1766. Tree of Coprimes LeetCode Solution in Java
class Solution {
public int[] getCoprimes(int[] nums, int[][] edges) {
int[] ans = new int[nums.length];
Arrays.fill(ans, -1);
List<Integer>[] tree = new List[nums.length];
// stacks[i] := (node, depth)s of nodes with value i
Deque<Pair<Integer, Integer>>[] stacks = new Deque[kMax + 1];
for (int i = 0; i < nums.length; ++i)
tree[i] = new ArrayList<>();
for (int i = 1; i <= kMax; ++i)
stacks[i] = new ArrayDeque<>();
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
tree[u].add(v);
tree[v].add(u);
}
dfs(tree, 0, /*prev=*/-1, /*depth=*/0, nums, stacks, ans);
return ans;
}
private static final int kMax = 50;
private void dfs(List<Integer>[] tree, int u, int prev, int depth, int[] nums,
Deque<Pair<Integer, Integer>>[] stacks, int[] ans) {
ans[u] = getAncestor(u, stacks, nums);
stacks[nums[u]].push(new Pair<>(u, depth));
for (final int v : tree[u])
if (v != prev)
dfs(tree, v, u, depth + 1, nums, stacks, ans);
stacks[nums[u]].pop();
}
private int getAncestor(int u, Deque<Pair<Integer, Integer>>[] stacks, int[] nums) {
int maxNode = -1;
int maxDepth = -1;
for (int i = 1; i <= kMax; ++i)
if (!stacks[i].isEmpty() && stacks[i].peek().getValue() > maxDepth && gcd(nums[u], i) == 1) {
maxNode = stacks[i].peek().getKey();
maxDepth = stacks[i].peek().getValue();
}
return maxNode;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
} // code provided by PROGIEZ
1766. Tree of Coprimes LeetCode Solution in Python
class Solution:
def getCoprimes(self, nums: list[int], edges: list[list[int]]) -> list[int]:
kMax = 50
ans = [-1] * len(nums)
tree = [[] for _ in range(len(nums))]
# stacks[i] := (node, depth)s of nodes with value i
stacks = [[] for _ in range(kMax + 1)]
for u, v in edges:
tree[u].append(v)
tree[v].append(u)
def getAncestor(u: int) -> int:
maxNode = -1
maxDepth = -1
for i, stack in enumerate(stacks):
if stack and stack[-1][1] > maxDepth and math.gcd(nums[u], i) == 1:
maxNode, maxDepth = stack[-1]
return maxNode
def dfs(u: int, prev: int, depth: int) -> int:
ans[u] = getAncestor(u)
stacks[nums[u]].append((u, depth))
for v in tree[u]:
if v != prev:
dfs(v, u, depth + 1)
stacks[nums[u]].pop()
dfs(0, -1, 0)
return ans # code by PROGIEZ
