Shortest Path between Cities Geeks For Geeks

Problem Link:

https://practice.geeksforgeeks.org/problems/shortest-path-between-cities/1#

(It is also the problem of the day for 28-05-2022)

Solution:

class Solution { 

    int shortestPath( int x, int y){ 

       int height=0;

       while(x!=y){

          if(x>y){

              x=x/2;

              height++;

          }

          else{

              y=y/2;

              height++;

          }

       }

       return height;

    }

}

Time Complexity:O(LogN)[GFG Time:0.12/1.16]

Space Complexity:O(LogN)

Auxiliary Space:O(1)

Approach Explained:

Here we will apply the concept of gcd(x,y).

It is so because

1. We will traverse the nodes from bottom to top. 

2. While traversing we will continuously keep on dividing node value by 2 which means we are moving from lower level to upper level.

3. We will do this till the time both value becomes equal and simultaneously keep on incrementing the height variable by 1.

Better consider an example:

              1
          /      \
        /          \
       2             3
     /   \         /   \
    4     5       6     7         
   / \   / \     / \   / \
  8  9  10 11   12 13 14 15

Here we have node value 2 which has children 4 and 5. (4/2==2 and 5/2==2)

Similarly, node value 6 has two children 12 and 13 (12/2==6 and 13/2==6)

It means a node with the value n will cover children having a value of one node as (2*n) and another node as (2*n+1).

So clearly if we keep on dividing node value by 2 we will keep going up and when the value of x==y means we have reached a common parent, at that time we will come out of the loop.

This height variable will then tell us the steps required to traverse from node x to node y or vice versa.

Here increment of the height variable by 1 indicates the change of level more precisely we have moved one level up.

(Retracing of the path of a node from node to its parent.)

Total Test Cases:310

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure😊"