We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Tree of Coprimes

Difficulty: Hard

Problem Description

There is a tree consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. Each node has a value associated with it. The task is to return an array where each element represents the closest ancestor of a node such that their values are coprime, or -1 if no such ancestor exists.

Key Insights

  • The tree structure allows for a depth-first search (DFS) approach to explore all nodes and their ancestors.
  • The coprimality condition can be efficiently checked using the greatest common divisor (GCD).
  • We can maintain a set of ancestor values as we traverse the tree to quickly check for coprime relationships.
  • The constraints indicate that the tree can be large, so an efficient algorithm is required.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree. Each node and edge is processed once. Space Complexity: O(n), due to the storage of the tree structure and the ancestor tracking.

Solution

The solution employs a depth-first search (DFS) to traverse the tree. As we visit each node, we maintain a list of ancestor values that we can check against the current node's value for coprimality. If a coprime ancestor is found, we record that ancestor; otherwise, we continue searching up the tree. The GCD function is used to check coprimality.

Code Solutions

from collections import defaultdict
from math import gcd

def coprimeAncestors(nums, edges):
    n = len(nums)
    tree = defaultdict(list)
    
    # Build the tree from edges
    for u, v in edges:
        tree[u].append(v)
        tree[v].append(u)

    def dfs(node, parent, ancestors):
        # Check coprimeness with ancestors
        closest_coprime_ancestor = -1
        for ancestor in reversed(ancestors):
            if gcd(nums[node], nums[ancestor]) == 1:
                closest_coprime_ancestor = ancestor
                break
        
        ans[node] = closest_coprime_ancestor
        
        # Add current node to ancestors
        ancestors.append(node)
        
        # Visit all children (DFS)
        for neighbor in tree[node]:
            if neighbor != parent:  # Avoid going back to the parent
                dfs(neighbor, node, ancestors)
        
        # Backtrack: remove the current node from ancestors
        ancestors.pop()
    
    ans = [-1] * n
    dfs(0, -1, [])
    return ans
← Back to All Questions