1766. Tree of Coprimes
Explanation:
The problem requires finding the closest ancestor of each node in the tree such that the values of the node and its ancestor are coprime. We can use a depth-first search (DFS) approach to traverse the tree while keeping track of the coprime ancestors.
- We can precompute all coprime values for numbers in the range [1, 50] with a sieve algorithm.
- During the DFS traversal, for each node, we iterate through all possible coprime values and check if any ancestor node has that coprime value.
- If we find a coprime ancestor, we update the closest coprime ancestor for the current node.
- We continue the DFS traversal until all nodes are processed.
Time Complexity: O(n * sqrt(max(nums[i]))), where n is the number of nodes and max(nums[i]) is the maximum value in the nums array. Space Complexity: O(n) for the adjacency list and coprime values.
:
class Solution {
public int[] getCoprimes(int[] nums, int[][] edges) {
int n = nums.length;
List<Integer>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
graph[u].add(v);
graph[v].add(u);
}
int[][] coprime = new int[50 + 1][0];
for (int i = 1; i <= 50; i++) {
List<Integer> list = new ArrayList<>();
for (int j = 1; j <= 50; j++) {
if (gcd(i, j) == 1) {
list.add(j);
}
}
coprime[i] = list.stream().mapToInt(Integer::intValue).toArray();
}
int[] ans = new int[n];
Arrays.fill(ans, -1);
dfs(0, -1, nums, graph, coprime, new ArrayList<>(), ans);
return ans;
}
private void dfs(int node, int parent, int[] nums, List<Integer>[] graph, int[][] coprime, List<Integer>[] nodeIndex,
int[] ans) {
int bestIndex = -1;
int bestDepth = -1;
for (int i : coprime[nums[node]]) {
if (!nodeIndex[i].isEmpty()) {
int index = nodeIndex[i].get(nodeIndex[i].size() - 1);
int depth = nodeIndex[i].size() - 1;
if (depth > bestDepth) {
bestDepth = depth;
bestIndex = index;
}
}
}
if (bestIndex != -1) {
ans[node] = bestIndex;
}
List<Integer> newList = new ArrayList<>();
for (int i : coprime[nums[node]]) {
List<Integer> copy = new ArrayList<>(nodeIndex[i]);
copy.add(node);
newList.add(i);
nodeIndex[i] = copy;
}
for (int child : graph[node]) {
if (child != parent) {
dfs(child, node, nums, graph, coprime, nodeIndex, ans);
}
}
for (int i : newList) {
nodeIndex[i].remove(nodeIndex[i].size() - 1);
}
}
private int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.