#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;
}
1 Like
Your function:
long int level(long int i)
{return (long int)(log10((double)i)/log10((double)2));}
gives wrong result. Actually its due to the lack of precision in calculation of log.
For instance, this function gives the level of 4 and 8 both as 2. But the correct answer is that level of 8 is 3. So, its basically due to the lack of precision in log calculation.
2 Likes
int level(long long index)
{
long long targetlevel=0;
while (index >>= 1)
++targetlevel;
return targetlevel;
}
In the above code, we keep dividing the above number by 2, till the number is >0, and we keep increasing count correspondingly. The count gives us the level of a node. There are no floating point calculations involved here, so there is no precision loss.
2 Likes
Hi, @atuljain10
Read the editorial Bintree editorial
After Each contest there are editorials for all the problems. Editorials can be found in the forum. Editorials explain the method/approach to solve the problem.
1 Like
http://code.hackerearth.com/72c7f6j
here is link to run this code on hackerearth.com and please tell how this code is incorrect .
ThankYou