Shortest distance in infinite tree

Shortest distance in infinite tree

  September 08, 2017    

---

Problem :

               1
           2      3
        4  5    6  7
    .  .  .  .   .  .  .  . 
 given two nodes with values x and y, the task is to find the length of the shortest path between the two nodes.


Idea :

As we know in tree implementation ,root can be find by dividing value by 2
Here we are using the same thing


Code:

public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
   int x=ab.nextInt();
   int y=ab.nextInt();
   if(x<y)
   { int temp=x;
   x=y;
   y=temp;
   }
   int c=0;
   while(x!=y)
   {
      ++c;
      if(x>y)
      x=x>>1;
      if(y>x)
      {y=y>>1;
          ++c;
      }
   }
   System.out.println(c);
}}