@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.
1 Like
#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;
}
Please tell why this code is wrong ?
1 Like
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!!
10 sec difference! 
I have followed the method in the editorial. But I am getting WA.
what could be wrong?
http://www.codechef.com/viewsolution/7022849
1 Like
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).
Could anyone give some test data?
1 Like
Plz write in a bit detail .
U have not explained what is k in here
when u said
ap=bp,p<=k
What is K ???
I don’t know why it is coming wa…I have tested it for all possible cases
link : CodeChef: Practical coding for everyone
As I understood , here k is value of the shared common ancestor of i and j. Or to understand it better follow this link
simplest solution that i came up with:
#include
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
long long int i,j,n=0;
cin>>i>>j;
while(i!=j)
{
if(i>j)
{
i=i/2;
n++;
}
if(j>i)
{
j=j/2;
n++;
}
}
cout<<n<<endl;
}
return 0;
}
7 Likes
ll -> long int or long long int
ll calc(ll a, ll b){
if(a == b)
return 0;
else if(a > b && a != 1){
if(a%2 == 0)
return 1+calc(a/2, b);
else
return 1+calc((a-1)/2, b);
}
else if(b>a && b != 1){
if(b%2 == 0)
return 1+calc(a, b/2);
else
return 1+calc(a, (b-1)/2);
}
}
Guys please explain me in the above explanation how ‘k’ value could 1.
Please explain me.
http://code.hackerearth.com/72c7f6j
here is link to run this code on hackerearth.com and please tell how this code is incorrect .
ThankYou
use long instead of int. As given in the question, 1 ≤ i,j ≤ 109.
try using
scanf( " %ld " , &valueToBeInserted );
Best editorial!! THANKS
https://www.codechef.com/viewsolution/24299424
https://www.codechef.com/viewsolution/24299478
here, 24299424 is getting TLE and 24299478 is getting AC but, all I have done is taken a block of code and made it a function. Why is this happening?
A very easy-to-understand answer for beginners.
vector<int> getBinary(int x){
vector<int>v;
while(x>0){
v.push_back(x&1);
x>>=1;
}
reverse(v.begin(),v.end());
return v;
}
int main(){
int t;
cin>>t;
while(t--){
int i,j;
cin>>i>>j;
vector<int>v1 = getBinary(i);
vector<int>v2 = getBinary(j);
int ct=0;
for(int i=0;i<min(v1.size(),v2.size());i++){
if(v1[i]==v2[i]){ct++;} else {
break;
}
}
cout<<v1.size() + v2.size() - 2* ct<<endl;
}
return 0;
}
can someone dry run for 2 and 8 ans’s coming 2 which is correct but while doing it i am getting 6;
binary of 2(10) and 8(1000) , so sz = min(2,4) = 2, in the loop all the elements are equal (from 0 to 2) so lca = 2;
therefore ans = size of 2 + size of 8 - 2lca = 2 + 8 - 22 = 10-4 = 6 its not coming 2 , can someone explain please 
got it i was taking the size of 8(1000) as 8 and not 4 sillly me got it.
can you explain your approach