Tree of Coprimes

Intuition

Problem Description

Like many other problems, let's figure out the input, limitation and output from the description.

The input of this problem is a tree where each node has a value. It is given by an array nums representing values of each node. And edges representing the edge between the edge[i][0] and edge[i][1].
The limitation is given by the definition Coprime, where the greatest common divisor(GCD) of 2 node values is 1.
The required output is the closest coprime anacestor for each node. The result should be returned by an array where result[i] is the index of node i's closest coprime anacestor.

Data Structure

Even if the input is a tree, since we are only given edges, we can use adjacent list to represent the tree, where adj[i] is a list of nodes who is node i's neighbors.

Basic Idea

The basic idea of this problem is to traverse the tree. And during the traversal, for each node, calculate the closest coprime anacestor. Now let's consider the time complexity of this basic solution.

To traverse a tree, we can use Depth-first Search (DFS). The basic time complexity of DFS is O(nodes.length + edges.length).
For each node, we need to go through all it's ancestors from bottom to top to check if they are coprime. The worst case would be there are no coprime in it's ancestors, and the time complexity of this step would be O(tree.depth). Since the tree is not a balanced tree, for it's depth, we need to consider it's the same as node number, which is O(nodes.length).
To check if 2 numbers are coprime, we would need to check all number which is less than or equal to the minimum number between the 2 numbers, to see if it's a common divisor of them. Time complexity of this step is O(num).

The overall time complexity would be:

O((nodes.length + edges.length) * nodes.length * max(nums))

The input range is given in the problem description.

nums.length == n

1 <= nums[i] <= 50

1 <= n <= 100,000

edges.length == n - 1

edges[j].length == 2

0 <= uj, vj < n

uj != vj

And the number of operations is:

O( (n + n) * n * len(nums) )
= O( n ** 2 * len(nums) )
= O( (10 ** 10) * 50 )
= O( 10 ** 11 )

This is high above standard which is 1,000,000.

Improvement

The basic solution spend too much time because there are too many operations. In this case, we can consider to pre-calculate something. So the time complexity would be O(pre) + O(solution).

One key point of this problem is that the range of each number is between 1 and 50. So

System Message: WARNING/2 (<string>, line 69)

Bullet list ends without a blank line; unexpected unindent.

we could calculate isCoprime for all integer pairs in time O(max(nums) ** 2) = O(2,500).

Then, for each node, instead of calculate through all it's ancestors, we maintain a array storing

System Message: WARNING/2 (<string>, line 72)

Bullet list ends without a blank line; unexpected unindent.

the closest anacestor for each number. And update this array for each node. This would only take O(max(nums)).

So now, the time complexity is:

O(max(nums) ** 2) + O(n + n) * O(max(nums))
= O(max(nums) ** 2) + O( n * max(nums) )
= O( max(nums) * (max(nums) + n) )
= O( 50 * (50 + 100,000) )
~= O( 5 * (10 ** 6) )
= O( 5,000,000 )

This would be a just fine time time complexity (around 1,000,000).

About Code

The method isCoprime is for calculating whether 2 numbers are coprime.
The method _dfs is the main part of the solution, which traverses the tree and calculate the closest coprime ancestor.
Variable candidates stores the cloeset coprime ancestor for each possible number, it's maximum length is 50.

Solution


class Solution:
    def getCoprimes(self, nums, edges):
        candidates = set(nums)
        coprime = {}
        for i in candidates:
            for j in candidates:
                coprime[(i, j)] = self.isCoprime(i, j)

        adj = [[] for _ in range(len(nums))]
        for p, q in edges:
            adj[p].append(q)
            adj[q].append(p)

        closestCoprime = [-1] * len(nums)
        candidates = {v: -1 for v in set(nums)}
        self._dfs(-1, 0, nums, adj, candidates, closestCoprime, coprime)
        return closestCoprime

    def isCoprime(self, i, j):
        if i == 1 or j == 1:
            return True
        if i == j:
            return False
        for c in range(2, min(i, j) + 1):
            if i % c == 0 and j % c == 0:
                return False
        return True

    def _dfs(self, parent, current, nums, adj, candidates, closestCoprime, coprime):
        closestCoprime[current] = candidates[nums[current]]

        tmp = {}
        for key in candidates.keys():
            if coprime[(nums[current], key)]:
                tmp[key] = candidates[key]
                candidates[key] = current

        for child in adj[current]:
            if child == parent:
                continue
            self._dfs(current, child, nums, adj, candidates, closestCoprime, coprime)

        for key in tmp.keys():
            candidates[key] = tmp[key]