Why was my solution ruled as wrong (BINTREE)?

general
,
1

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX 1000000000
#define maxn 100000
 
int main (void) {
int N;
int i, j, br=0;
int k=0, flag=0, pom;
scanf("%d", &N);
if (N>maxn) exit(2);
while(k<N) {
br=0;
flag=0;
scanf("%d %d", &i, &j);
if((i>MAX)|| (j>MAX)) exit(1);
if(j>i) {
pom=j;
while (pom>0) {
if (pom==i){
flag=1;
break;
}
pom/=2;
br++;
}
}
else if (i>j) {
pom=i;
while(pom>0){
if(pom==j){
flag=1;
break;
}
pom/=2;
br++;
}
}
if(flag==0 && i!=j){
br=0;
while(j>1 || j!=i || i>1) {
if(j>1){
j/=2;
br++;
}
if(i>1){
i/=2;
br++;
}
}
}
printf("%d\n", br);
k++;
}
return 0;
}
2

for test cases with both numbers on the same side of the root and are only connected with a common ancestor you are getting wrong answer.
eg:-
4 90 answer is 6 you are getting 8

in the 44th line the while loop is having conditions combined with || rather than &&…
thats where you got wrong.

You can find the solution by just using the while loop in the 44th line, i.e by adding the path till both of them meet their common ancestor.

while(j!=i)
if j>i
j=parent(j)
path++
else
i=parent(i)
path++

1 Like