Largest Tree Uber OA

Question

We are given a perfect N-ary tree where N denotes the number of children a node has. The tree has infinite nodes. You are given two nodes x,y. You need to find the shortest path between these two nodes.
Note: The maximum value of x,y is 1e12.

Solution

As you know, perfect N-ary tree has children in following pattern:

Parent : i
Childs : i*N + 1, i*N + 2, i*N + 3 ....... i*N + N
So, if child is c, parent is : (c-1)/N

The worst case scene is when x is 1e12 and n = 2. In these case the depth of this node will be log(x) ~ 40. So we can compute all ancestors of this node. In similar way compute all ancestors of y. Find the LCA(x,y) and then you know dist(LCA,x) + dist(LCA,y) is your answer.

External Solution Link: https://pastebin.com/2gFVt4H7

Leave a Reply