0
$\begingroup$

Problem Statement : Given a tree with N nodes rooted at node 1. Each node is associated with a value. Determine the closest ancestor that contains the value coprime to the current node value. (Note that it is node value and not node number.)

Here is what I did :

Define the lists as : adj[ ] is the adjacency list (a list of lists which is constructed when taking inputs from the user).

Create a list parent[ ] that stores the parent of each node. This can be done in O(N) time.

Our main algorithm is to start at node 1 and mark it as ans[1] = -1 since it can not have an ancestor. Traverse through the nodes in the DFS manner. Check for the coprime ancestor by setting a variable v and a while loop such that if gcd(node, v) == 1 : ans[node] = v else make v = parent[v]. In this way, we check if the parent is coprime, if not, we check if parent[parent] is coprime and so on, till we hit the base case.

Pseudocode for the main problem :

ans[1] = -1
parent[1] = 0
def dfs(root) :
        loop node in adj[root] :
                v = root
                while (5 > 0) :
                    if gcd(val[node],val[v]) == 1 :
                        ans[node] = v
                        dfs(node)
                    else :
                        v = parent[v]
                        if v == 0 :
                            ans[node] = -1
                            dfs(node)

The GCD can be evaluated in O(log_2 max(val[node])) time. The while loop runs in a time proportional to O(depth(node)). Suppose b is the max branching factor of the graph. Then, the overall complexity will be O(|V| + |E| + sum(b^{r <= d} log_2 max(val[node]))) = O(N log_2 max(val)).

1. Is there a more optimized code (average time/space complexity wise)?

2. Is the algorithm correct or there are loop holes in the logic or maybe in some boundary cases?

$\endgroup$
1
  • $\begingroup$ "Suppose b is the max branching factor of the graph." Did you mean "b is the min branching factor of the graph."? Otherwise, a linear tree of values $1, 2, 2, 2, \cdots, 2$ will be processed in $O(n^2)$ time by your algorithm. $\endgroup$ – John L. Dec 15 '20 at 4:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.