Ninja And Numbers

Moderate
0/80
Average time to solve is 40m
0 upvote
Asked in companies
UberSoft Suave

Problem statement

Ninja is learning tree data structures. His friend is helping him learn by giving him problems to solve. He gives him a tree with N nodes numbered from 0 to N - 1 in the form of a parent array parent where parent[i] is the parent of the ith node. The root of the tree is node 0. Now Ninja has to find the kth ancestor of a given node. The kth ancestor of a tree node is the kth node in the path from that node to the root node.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer ‘T’, denoting the number of test cases.

The second line of each test case contains a positive integer ‘N’, denoting the number of nodes.

The third line of each test case contains the parent array.

The fourth line of each test case contains a node value and k value.
Output Format : 
The first and only line of each test case contains an integer denoting the kth ancestor.
Note: 
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10
1 <= k <= N <= 5 * 10 ^ 4
0 <= node < N
0 <= parent[i] < N

Time limit: 1 second
Sample Input 1:
2
7
-1 0 0 1 1 2 2
3 1
7
-1 0 0 1 1 2 2
5 2
Sample Output 1:
1
0
Explanation for Sample Output 1:

1

In the first test case, it is visible from the figure that the 1st ancestor of a node with the value of 3 is the parent node of 3. Parent of 3 is 1.So we return 1 as our answer. 

In the second test case, the first ancestor of the node with the value 5 is 2. Now to find the 2nd ancestor of this node, we find the 1st ancestor of the parent of this node. Now, 1st ancestor of 2 is 0. So we return 0 as our answer
Sample Input 2:
2
7
-1 0 0 1 1 2 2
4 2
7
-1 0 0 1 1 2 2
6 1
Sample Output 2:
 0
 2
Hint

Do some precomputation. Can you use the concept that every number can be represented as the sum of power of 2?

Approaches (2)
Binary Lifting

This problem can be solved using a technique known as binary lifting. We need to compute each node, which is exactly 2^i nodes above a given node, and we will store it in an array up[node][i]. Now we will run a DFS to fill this for each node. To compute up[node][i], we can find the node which is 2^i-1 steps above the node which is 2^i - 1 above the current node, hence up[node][i] = up[up[node][i-1]][i-1]. Each query can be answered in log n by treating k as a binary number and moving 2^i steps upward for each set bit in k.

 

The steps are as follows:   

  • Initialize vector graphs to store the edges of the tree.
  • Run a loop from i =1 to i = N - 1:
    • Initialize u with parent[i] to store the parent node of the current node.
    • Store in graph[u] the current node i.
  • Perform a recursive function dfs on this tree.
    • Store a pointer p = -1 to indicate it is the root node.
    • If p is not -1then store in par[src][[0], the value of p.par signifies the ith ancestor of a given node ‘src’.
    • Then run a loop from j = 1 to (1<<j) <=h:
      • Store in par[src][j] the value of par[par[src][j-1]][j-1].
    • We iterate over all the child nodes of the present node and recursively perform dfs.
  • We call the function getKthAncestor to get the kth ancestor.
    • We run a loop from i = 31 to 0:
    • If the value of the node is -1, then break
    • If (1<<i)&k then we sore the value par[node][i] in node.
  • Finally, we return the node, which is the kth ancestor.
Time Complexity

O(Nlog N), where ‘N’ is the number of nodes

 

The time required to preprocess all the nodes takes O(NlogN) time. So the overall complexity is O(Nlog N) If there were many queries then this approach is very efficient as each query requires O(logN) operation.

Space Complexity

O(Nlog N), where ‘N’ is the number of nodes

 

The space required to preprocess and store all the nodes takes O(NlogN) time. So the overall complexity is O(log N).

Code Solution
(100% EXP penalty)
Ninja And Numbers
Full screen
Console