Last Updated: 16 Apr, 2021

Closest Coprime Ancestor

Hard

Asked in company

Solve now

Problem statement

You are given an integer array, ‘NODES’ and a 2 - D array, ‘EDGES’ to represent a tree (i.e. a connected undirected graph) consisting of ‘N’ nodes (numbered from 0 to N - 1) and exactly (N - 1) edges where the EDGES[ i ] = {Ui, Vi} represents an edge between the ‘U’th and ‘V’th node. Each node has a value associated with it, stored in the ‘NODES’ array where ‘NODES[ i ]’ represents the ‘i’th node’s value.

Your task is to return an ‘N’ size array, ‘RESULT’, where RESULT[ i ] = the closest ancestor to ‘i’th node such that NODES[ i ] and NODES[RESULT[ i ]] are coprime, else if no such ancestor found, RESULT[ i ] = -1.

Note :

1) The value associated with the ‘ROOT’ node of the tree is considered zero.
2) Two integers ‘A’ and ‘B’ are coprime if the only positive integer that evenly divides (is a divisor of) both of them is 1, i.e., GCD(A, B) = 1 where GCD(A, B) is the greatest common divisor of ‘A’ and ‘B’.
3) Any node on the shortest path from ‘i’th node to the root is the ancestor of the ‘i’th node.
4) A node is not considered an ancestor of itself.
5) A graph is said to be a connected undirected graph if all the edges are bidirectional and there is a path between every pair of distinct vertices of the graph.

Input Format :

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains an integer ‘N’ representing the number of nodes in the tree.

The second line of each test case contains ‘N’ space-separated integers representing the elements of the ‘NODES’ array.

The next ‘N - 1’ lines of each test case contain two space-separated integers, ‘U’ and ‘V’, representing an edge between ‘U’ and ‘V’.

Output Format :

For each test case, print a ‘N’ size array, ’RESULT’ where RESULT[i] = the closest ancestor to ‘i’th node such that NODES[ i ] and NODES[RESULT[ i ]] are coprime, else if no such ancestor found, RESULT[ i ] = -1.

The output of each test case will be printed in a separate line.

Constraints :

1 <= T <= 5
1 <=  N <= 2000
|EDGES[ i ]| = 2
1 <= NODES[ i ] <= 20
EDGES[ i ] = {Ui, Vi} where 0 <= Ui, Vi < N
Ui != Vi

Where ‘|EDGES[ i ]| is the length of ‘i’ the array in ‘EDGES’, ‘NODES[ i ]’ is the ‘i’th element in the ‘NODES’ array, ‘EDGES[ i ]’ is the ‘i’th array of two integers ‘Ui’ and ‘Vi’ in the 2 - D array, ‘EDGES’.

Time limit: 1 sec

Note :

 You do not need to print anything, it has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

The idea is to use the brute force approach to traverse the tree using DFS. At every node, we will go through all of its ancestors and check if they are coprime, and update the ‘RESULT’ array.

For this purpose, we will first build an adjacency list using ‘EDGES’ and then perform the DFS.

Algorithm:

Declare a vector of integers, ‘RESULT’ of size ‘N’ to store the closest coprime ancestor for every node.
Declare a vector of integers, ‘ANCESTORS’ to store the list of ancestors for every node.
Declare a vector of vector of integers, ‘ADJLIST’ to store the adjacency list representation of the given tree.
Run a loop for every vector of integers, ‘EDGE’ in the ‘EDGES’.
- Push ‘EDGE[ 1 ]’ in the ‘ADJLIST[EDGE[ 0 ]]’.
- Push ‘EDGE[ 0 ]’ in the ‘ADJLIST[EDGE[ 1 ]]’.
Call the ‘dfs’ function.
In the end, return ‘RESULT’.

Description of ‘dfs’ function :

This function will take six parameters:

NODES: A vector of integers representing the values associated with every node.
ADJLIST: A vector of vector of integers representing the adjacency list of the given tree.
ANCESTORS: A vector of integers representing the list of ancestors for every node.
CURRENT: An integer representing the current node for which the closest coprime ancestor has to be found.
PARENT: An integer representing the parent of the ‘CURRENT’ node.
RESULT: a vector of integers to store the closest coprime ancestor for every node.

void dfs(NODES, ADJLIST, ANCESTORS, CURRENT, PARENT, RESULT):

Assign -1 to the ‘RESULT[CURRENT]’ indicating ‘CURRENT’ has no coprime ancestor.
Run a loop for every ‘ANCESTOR’ in the ‘ANCESTORS’.
Declare a variable ‘VALUEOFANCESTOR’ and assign ‘NODES[ ANCESTOR ]’ to it.
Declare a variable ‘VALUEOFCURRENT’ and assign ‘NODES[ CURRENT ]’ to it.
If GCD of ‘VALUEOFANCESTOR’ and ‘VALUEOFCURRENT’ that shows that we found a coprime ancestor of ‘CURRENT’ node. So,
- Assign ‘ANCESTOR’ to ‘RESULT[ CURRENT ]’.
Push ‘CURRENT’ to the ‘ANCESTORS’.
Run a loop for every ‘CHILDNODE’ in ‘ADJLIST[ CURRENT ]’.
- If ‘CHILDNODE’ is not equal to ‘PARENT’
  - Call ‘dfs’ by updating ‘CURRENT’ as ‘CHILDNODE’ and ‘PARENT’ as ‘CURRENT’.
Pop the last element from ‘ANCESTORS’.

Solve now

02 Approach

Since node values can range from [1, 20]. So even in the worst case, we do not have to check more than 20 ancestors for each node. So, initially, it was O(N) when we were checking every ancestor in the tree. Now, it becomes O(20), i.e., a constant operation.

For this purpose, we will create a lookup table, ‘COPRIMELOOKUP’. For every number in the range [1, 20], we will store its coprimes from the range [1, 20] in the ‘COPRIMELOOKUP’.

Now, we will do the DFS traversal, and for every node, instead of looking for all the ancestors, we will enumerate all of its coprimes from the ‘COPRIMELOOKUP’, and check if it is within our ancestors. We will do it for all the coprimes and store the closest ancestor in the ‘RESULT’ for that node.

Algorithm:

Declare a const integer variable, ‘MAX_NODE_VAL’ globally and initialize it with 20.
Declare a vector of integers, ‘RESULT’ of size ‘N’ to store the closest coprime ancestor for every node.
Declare a vector of pair integers, ‘ANCESTORS’ of size ‘MAXNODEVAL + 1’ to store the list of ancestors for every node. The first value of ‘ANCESTORS’ will be index and the second value will be its depth. Initialize all the values of index and depth by -1.
Declare a vector of vectors of integers, ‘ADJLIST’ of size ‘N’ to store the adjacency list representation of the given tree.
Declare a vector of vectors of integers, ‘COPRIMELOOKUP’ of size ‘MAXNODEVAL + 1’ to store the list of coprimes for every number.
Run a loop from i = 0 to i = MAX_NODE_VAL.
- Run a loop from j = 0 to j = MAX_NODE_VAL.
  - If the GCD of ‘i’ and ‘j’ is equal to 1.
    - Insert ‘j’ in ‘COPRIMELOOKUP[ i ]’.
Run a loop for every vector of integers, ‘EDGE’ in the ‘EDGES’.
- Push ‘EDGE[ 1 ]’ in the ‘ADJLIST[EDGE[ 0 ]]’.
- Push ‘EDGE[ 0 ]’ in the ‘ADJLIST[EDGE[ 1 ]]’.
Call the ‘dfs’ function.
In the end, return ‘RESULT’.

Description of ‘dfs’ function :

This function will take seven parameters:

NODES: A vector of integers representing the values associated with every node.
ADJLIST: A vector of vector of integers representing the adjacency list of the given tree.
COPRIMELOOKUP: A vector of vector of integers that stores the list of coprimes for every number.
ANCESTORS: A vector of pair integers representing the list of ancestors for every node.
CURRENT: An integer representing the current node for which the closest coprime ancestor has to be found.
PARENT: An integer representing the parent of the ‘CURRENT’ node.
RESULT: A vector of integers to store the closest coprime ancestor for every node.

void dfs(NODES, ADJLIST, COPRIMELOOKUP, ANCESTORS, CURRENT, PARENT, RESULT):

Declare three integer variables, ‘CLOSESTANCESTOR’, ‘MAXDEPTH’, ‘VALUE’. Initialize the ‘CLOSESTANCESTOR’ and ‘MAXDEPTH’ by -1 and ‘VALUE’ by ‘NODES[ CURRENT ]’. The ‘CLOSESTANCESTOR’ will store the index of closest ancestor for the ‘CURRENT’ node, ‘MAXDEPTH’ will store the maximum depth of the ‘CLOSESTANCESTOR’ and ‘VALUE’ stores the value associated with the ‘CURRENT’ node.
Run a loop for every ‘COPRIME’ in the ‘COPRIMELOOKUP[ VALUE ]’.
If ‘ANCESTORS[COPRIME].SECOND’ > ‘MAXDEPTH’ that shows that the current ancestor is closer than the ‘CLOSESTANCESTOR’. So,
- Update ‘CLOSESTANCESTOR’ by ‘ANCESTORS[ COPRIME ].first’.
- Update ‘MAXDEPTH’ by ‘ANCESTORS[COPRIME].SECOND’.
Update ‘RESULT[ CURRENT]’ by ‘CLOSESTANCESTOR’.
Declare a variable of pair of integers, ‘LASTVALUE’ and assign ‘ANCESTORS[ VALUE ]’ in it.
Update ‘ANCESTORS[ VALUE ]’ by ‘{CURRENT, DEPTH}’.
Run a loop for every ‘CHILDNODE’ in ‘ADJLIST[ CURRENT ]’.
- If ‘CHILDNODE’ is not equal to ‘PARENT’
  - Call ‘dfs’ by updating ‘CURRENT’ as ‘CHILDNODE’ and ‘PARENT’ as ‘CURRENT’.
Update ‘ANCESTORS[ VALUE ]’ by ‘LASTVALUE’.

Solve now