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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Tree of Coprimes

Number: 1875

Difficulty: Hard

Paid? No

Companies: Uber, Google

Problem Description

We are given a tree with n nodes (numbered 0 to n-1) and n-1 edges. Each node i has value nums[i]. The root is node 0. For every node, we must find the closest ancestor (on the unique path from the node to the root, excluding the node itself) such that the value of the ancestor and the value at node i are coprime (i.e. their gcd is 1). If no such ancestor exists, we return -1 for that node.

Key Insights

  • Use Depth-First Search (DFS) to process nodes in a path-aware manner.
  • Maintain a tracking structure for the last seen occurrence (along the current path) for every possible value from 1 to 50.
  • For each node, iterate over the possible values that are coprime with nums[node] (using a precomputed coprime check table) and select the one with the maximum depth (i.e. closest ancestor).
  • Leverage backtracking to undo changes in the tracking structure after processing subtrees.
  • Precompute coprime relationships for numbers 1 through 50 to optimize repeated gcd computations.

Space and Time Complexity

Time Complexity: O(n * 50) in the worst-case scenario, as each node iterates through at most 50 candidate values. Space Complexity: O(n + 50) due to the DFS recursion stack (O(n) in worst-case) plus the tracking table of fixed size 51.

Solution

We approach this problem by performing a DFS from the root node. As we enter a node, we examine the current DFS path by checking our tracking structure that stores the most recent occurrence (both depth and node index) for each value seen so far. For the current node, iterate over all values 1 to 50 that are coprime with its value, and determine the candidate ancestor with the greatest depth (i.e. closest in the DFS path). Before recursing into child nodes, update the tracker for the current node’s value. After the recursion returns, backtrack by restoring the original state of the tracker. This ensures that the answer for each node is based only on its ancestors in the DFS tree.

Code Solutions

def treeOfCoprimes(nums, edges):
    from math import gcd
    n = len(nums)
    # Build the tree as an adjacency list.
    tree = [[] for _ in range(n)]
    for u, v in edges:
        tree[u].append(v)
        tree[v].append(u)
    
    # Precompute coprimality for numbers 1 to 50
    coprime = [[False] * 51 for _ in range(51)]
    for i in range(1, 51):
        for j in range(1, 51):
            coprime[i][j] = (gcd(i, j) == 1)
    
    ans = [-1] * n
    # lastOccurrence[x] = (depth, node) for the last occurrence of number x along current DFS path.
    lastOccurrence = [(-1, -1)] * 51
    
    def dfs(node, parent, depth):
        maxDepth = -1
        ancestor = -1
        for value in range(1, 51):
            if coprime[nums[node]][value]:
                occDepth, occNode = lastOccurrence[value]
                if occNode != -1 and occDepth > maxDepth:
                    maxDepth = occDepth
                    ancestor = occNode
        ans[node] = ancestor

        # Backup current occurrence for nums[node] and update it.
        prev = lastOccurrence[nums[node]]
        lastOccurrence[nums[node]] = (depth, node)
        
        for child in tree[node]:
            if child != parent:
                dfs(child, node, depth + 1)
        
        # Restore the previous state (backtracking)
        lastOccurrence[nums[node]] = prev

    dfs(0, -1, 0)
    return ans

# Example usage:
nums = [2, 3, 3, 2]
edges = [[0, 1], [1, 2], [1, 3]]
print(treeOfCoprimes(nums, edges))
← Back to All Questions