Shortest Path in Binary Trees Codechef Solution|Problem Code: BINTREE

Shortest Path in Binary Trees Codechef Solution: Hello coders, today we are going to solve Shortest Path in Binary Trees Codechef Solution.

Codechef solutions

Problem

Consider an infinite full binary tree (each node has two children except the leaf nodes) defined as follows. For a node labelled v its left child will be labelled 2*v and its right child will be labelled 2*v+1. The root is labelled as 1.

You are given N queries of the form i j. For each query, you have to print the length of the shortest path between node labelled i and node labelled j.

Input

First line contains N, the number of queries. Each query consists of two space separated integers i and j in one line.

Output

For each query, print the required answer in one line.

Constraints

  • 1 ≤ N ≤ 105
  • 1 ≤ i,j ≤ 109

Example

Input:
3
1 2
2 3
4 3
Output:
1
2
3

Explanation

For first query, 1 is directly connected to 2 by an edge. Hence distance 1.

Shortest Path in Binary Trees- CodeChef Solution in JAVA

import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
	    try{
	Scanner sc = new Scanner(System.in);
	int t = sc.nextInt();
	while(t-->0){
	    int x = sc.nextInt();
	    int y = sc.nextInt();
	    int count=0;
	    while(x!=y){
	        if(x > y){
	            x=x/2;
	        }
	        else{
	            y=y/2;
	        }
	        count++;
	    }
	    System.out.println(count);
	}
	    }catch(Exception e){
	        return;
	    }
	}
}

Shortest Path in Binary Trees – CodeChef Solution in CPP

#include <iostream>
using namespace std;
int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--){
	    int a,b;
	    int count=0;
	    cin>>a>>b;
	    while(a!=b){
	        if(a>b){
	            a /=2;
	            count ++;
	        }
	        else{
	            b /=2;
	            count++;
	        }
	    }
	    cout<<count<<endl;
	}
	return 0;
}

Shortest Path in Binary Trees – CodeChef Solution in Python

if __name__ == "__main__":
    n = int(input())
    for i in range(n):
        i,j = list(map(int, input().split()))
        maxi = max(i,j)
        mini = min(i, j)
        count = 0
        while(True):
            if(maxi == mini):
                break
            else:
                maxi = maxi//2
                count +=1
                if(maxi != max(maxi, mini)):
                    maxi,mini = mini,maxi
        print(count)

Disclaimer: The above Problem (Shortest Path in Binary Trees) is generated by CodeChef but the solution is provided by  Chase2learn.This tutorial is only for Educational and Learning purpose.

Leave a Comment