### PROBLEM LINK:

**Author:** Lalit Kundu

**Tester:** Shiplu Hawlader and Mahbubul Hasan

**Editorialist:** Lalit Kundu

### DIFFICULTY:

EASY

### PREREQUISITES:

Binary Tree

Lowest Common Ancestor

### PROBLEM:

Given infinite full binary tree (each node has two children except leaf nodes), for queries of form (i,j) [i,j <= 10^9] print the length of shortest path between nodes labelled i and j.

Root is labelled 1. For each node labelled v, it’s left child is labelled 2*v and right child, 2*v+1.

### QUICK EXPLANATION:

We convert i,j to base 2 (without leading zeroes)

Let i in base 2 be = a_{1}a_{2}…a_{n}

Let j in base 2 be = b_{1}b_{2}…b_{m}

If a_{p}=b_{p} for all p<=k, then our answer is (n+m-2*k).

### EXPLANATION:

If we are at a node labelled v, if we move left we get 2*v ie. append a 0 to binary representation of v. If we move right we get 2*v+1 ie. append a 1 to binary representation of v. Thus from binary value of a node v, we completely know the path taken from the root.

For example, Node 10 in binary is 1010, here first 1 is root node, next is 0, means a left turn, next 1 means are right child, next 0 means a left child.

We convert i,j to base 2 (without leading zeroes)

Let i in base 2 be = a_{1}a_{2}…a_{n}

Let j in base 2 be = b_{1}b_{2}…b_{m}

If a_{p}=b_{p} for all p<=k, means their Lowest Common Ancestor(LCA) in binary is a_{0}a_{1}…a_{k}. So the distance between i and j is dist(i,LCA(i,j))+dist(j,LCA(i,j)).

Since i in base 2 has n digits, the distance between i and LCA(i,j) will be (n-k). Since those are the extra steps taken from LCA moving towards node.

Therefore our answer is (n-k)+(m-k).

For example, i=10, j=13.

i in base2 = 1010

j in base2 = 1101

So, k=1 and our answer is 4-1+4-1=6.

Complexity for each query= log2(i)+log2(j).

### AUTHOR’S AND TESTER’S SOLUTIONS:

To be updated soon.