PROBLEM LINK:Author: Lalit Kundu DIFFICULTY:EASY PREREQUISITES:Binary Tree PROBLEM: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. QUICK EXPLANATION:We convert i,j to base 2 (without leading zeroes) 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. Complexity for each query= log2(i)+log2(j). AUTHOR'S AND TESTER'S SOLUTIONS:To be updated soon.
This question is marked "community wiki".
asked 14 Apr '14, 15:07

simplest solution that i came up with: include<iostream>using namespace std; int main() { int t; cin>>t; while(t) { long long int i,j,n=0; cin>>i>>j;
}
link
This answer is marked "community wiki".
answered 27 Oct '16, 23:00

@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. answered 14 Apr '14, 21:49

include <stdio.h>include<math.h>long int poww(long int to) { if(to==0) return 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) {
} Please tell why this code is wrong ? answered 19 Apr '14, 13:52
http://code.hackerearth.com/72c7f6j here is link to run this code on hackerearth.com and please tell how this code is incorrect . ThankYou
(19 Apr '14, 14:08)

I have followed the method in the editorial. But I am getting WA. what could be wrong? http://www.codechef.com/viewsolution/7022849 answered 25 May '15, 19:37

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? answered 16 Jun '15, 22:07

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! :p answered 24 Apr '14, 19:03

Why is my code incorrect? answered 01 May '14, 18:18

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 ??? answered 25 Dec '15, 21:42

I don't know why it is coming wa...I have tested it for all possible cases link : https://www.codechef.com/viewsolution/10129222 answered 19 May '16, 16:22
use long instead of int. As given in the question, 1 ≤ i,j ≤ 10^{9}. scanf( " %ld " , &valueToBeInserted );
(08 Jul '16, 20:46)

As I understood , here k is value of the shared common ancestor of i and j. Or to understand it better follow this link http://www.geeksforgeeks.org/lowestcommonancestorbinarytreeset1/ answered 21 Jul '16, 17:05

Guys please explain me in the above explanation how 'k' value could 1. Please explain me.
Best editorial!! THANKS