Shortest Path in Binary Trees Codechef Solution

Hello Programmers In this post, you will know how to solve the Shortest Path in Binary Trees Codechef Solution. The Problem Code: BINTREE.

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for 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 ≤ 10⁵
• 1 ≤ i,j ≤ 10⁹

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;
	    }
	}
}

report this adShortest 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)

report this ad

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

Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.

Next: Yet Another Flipping Problem Codechef Solution