## khatribalak

BAN USER- 0of 0 votes

AnswersWe are given a undirected tree with N (1 to N) nodes rooted at node 1. Every node has a value assigned with it, represented by array - A[i] where i:[1:N].

- khatribalak in United States

We need to answer Q queries of type : -> V X : longest length of the common prefix between V and any ancestor of X including X, in their binary representation of 62-bit length.

Common prefix between 2 numbers is defined as:

Example :

4: 0..................0100 (62-bit binary representation)

6: 0..................0110

Considering both as 62-bit in it's binary representation.

Longest length of the common prefix is: 60 (as 60 left most bits are same.)

Now we are given the N (num nodes), edges, nodes values (A[i]) and queries, and we need to answer each query in optimal time.

Constrains :

N <= 10^5, number of nodes

A[i] <= 10^9, value of each node

Q <= 10^5 ,number of queries

Edge[i] = (i, j) <= N

Approach :

Create tree and track the immediate parent of each node.

for Each Query : [V, X], traverse each node n(in the path from X to root) and XOR each node's values with V and find the most significant set bit for each of the XOR operation and pick the minimum one among all of them.

So the result for Query : [V, X] : 62 - (1 + Step-2 result).

Is there any other efficient way to solve this problem? As the above approach in worst case takes O(n^2) time.| Report Duplicate | Flag | PURGE

Hi5 SDE1

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.