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 = a1a2…an
Let j in base 2 be = b1b2…bm
If ap=bp 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 = a1a2…an
Let j in base 2 be = b1b2…bm
If ap=bp for all p<=k, means their Lowest Common Ancestor(LCA) in binary is a0a1…ak. 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.
@pandu_49: i(10) in binary is 1010 and j(13) in binary is 1101, only for p<=1(k) is ap=bp true.
Another example, i(8) in binary is 1000 and j(2) in binary is 10, only for p<=2(k) is ap=bp true.
One more, i(10) in binary is 1010 and j(11) in binary is 1011, only for p<=3(k) is ap=bp true.
#include <stdio.h>
#include<math.h>
long int poww(long int to)
{
if(to==0)
return 1;
return 2*poww(to-1);
}
long int other_path(long int h,long int l)
{
long int path=0;
while(h!=l){
path+=2;
h/=2;l/=2;
}
return path;
}
long int level(long int i)
{return (long int)(log10((double)i)/log10((double)2));}
int main(void) {
long int t;
scanf("%ld",&t);
long int i,j,l_i,l_j,l_df,ans;
while(t-- > 0)
{
scanf("%ld %ld",&i,&j);
if(i>j)
{i=i+j; j=i-j; i=i-j;} // assigning max(j,i) to j and other i is always smaller one
l_i=level(i);
l_j=level(j);
l_df=l_j-l_i;
ans = l_df + other_path(j/poww(l_df),i);
/*bring them to same level and then decrease them to the common parent*/
printf("%ld\n",ans);
}
return 0;
A simple yet an elegant solution on the basis of a simple observation. Helped to relate the binary tree structure to its binary representation and actually how the the LCA method inherently works on this principle! Cheers!
Btw this also made me realize the effect of using cin/cout compared to scanf/printf!! http://www.codechef.com/status/BINTREE,tukku26
10 sec difference!
I tried all edge cases I could imagine, and have no idea where my logic is going wrong. I didn’t assume the numbers as binary numbers (as you did here though).
