D
DevExCode

LeetCode 1766: Tree of Coprimes Solution

Master LeetCode problem 1766 (Tree of Coprimes), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

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.

  1. We can precompute all coprime values for numbers in the range [1, 50] with a sieve algorithm.
  2. During the DFS traversal, for each node, we iterate through all possible coprime values and check if any ancestor node has that coprime value.
  3. If we find a coprime ancestor, we update the closest coprime ancestor for the current node.
  4. 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.

:

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1766 (Tree of Coprimes)?

This page provides optimized solutions for LeetCode problem 1766 (Tree of Coprimes) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1766 (Tree of Coprimes)?

The time complexity for LeetCode 1766 (Tree of Coprimes) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1766 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1766 in Java, C++, or Python.

Back to LeetCode Solutions