Why Wrong Answer : My BINTREE code?

general
,
1

#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
2

http://code.hackerearth.com/72c7f6j

here is link to run this code on hackerearth.com and please tell how this code is incorrect .

ThankYou

3

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. :slight_smile:

2 Likes
4 
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
5

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