Like many other problems, let's figure out the input, limitation and output from the description.
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.
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.
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.
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).
we could calculate isCoprime for all integer pairs in time O(max(nums) ** 2) = O(2,500).
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).
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]