CodeVita 2020 Solutions :> #1 Path Through Graph

 

Path Through Graph

Problem Description:  You are given two natural numbers. Imagine these natural numbers as node on a graph. On this graph, a number is connected to its largest factor other than itself.
you have to find the shortest path between them and print the number of edges on that path.

Example 1: Input: 2 4

                        output: 1                   Explanation: 4<-->2

Example 2: Input: 18 19

                        output: 4                    Explanation: 18<-->9<-->3<-->1<-->19

Example 3: Input: 9 9

                        output: 0

Constraints:

      0<= N1, N2 <=10^9

Example1 : Input: 15689 28

                        output: 5

C++ solution:

#include<iostream>

#include<map>

using namespace std;

int get(int x)

{

    for(int i=2;i*i<=x;i++)        //get function return largest factor other than x

    {

        if(x%i==0)

            return x/i;

    }

    return 1;

}

int main()

{

    int x,y;  //taking input

    cin>>x>>y;

    if(x<y)                 //swapping because want my first number to be bigger

        swap(x,y);

    if(x==y)

    {                       //corner case when both number are same print 0 and return

        cout<<0;

        return 0;

    }    

    map<int,int> m;

    int c=0;                    //store into map steps from x to all factors in decreasing order

    while(x!=1)

    {

        c++;

        x=get(x);

        m[x]=c;

    }

    c=0;

    while(!m.count(y))

    {                       //if we find y in map simply return m[y] else travel from y to common factor

        c++;

        y=get(y);                                                    //now let's run it

    }

    cout<<c+m[y];

    return 0;

}

Also, read other solutions for CodeVita : Unblocker

Thank you

Please also visit my Youtube channel for more updates: Code With Yash