Home » Interview coding problems/challenges

PPATH - Prime Path Problem

Here, we are going to find the solution of PPATH - Prime Path Problem using various approaches.
Submitted by Divyansh Jaipuriyar, on April 13, 2021

Description: The problem has been asked in competitive programming, but the concept used in this problem has been featured in interview rounds of many top tech companies.

Problem Statement: You are given two prime numbers n and m of 4 digits each, you need to convert n into m in the minimum number of steps, in each step you can change one of the digits of the number n such that a resulting number is also a prime number. Finally, give the number of minimum steps that you would take to complete the task if you can't change n to m then print "Impossible".

Problem Description: Given problem wants you to convert a number N1 to N2 keeping in mind that in each step the number you obtain should also be a prime number and if you are not able to change then you simply print ("Impossible") otherwise Print the minimum number of steps that you took to complete the conversion.

Input: The first line of the input consists of a T number of test cases, each test case contains two numbers n and m.

Output: In each new line print the minimum number of steps that you would take to complete the task.

Example:

Input:
T = 1
N = 1033, M = 8179

Output:
6
Explanation:
The conversion is done in the following way:
1033 -> 1733 -> 3733 -> 3739 -> 3779 -> 8779- > 8179.

Input:
T = 1
N = 11, M = 23

Output:
2

Explanation:
The conversion is done in the following way: 
11 -> 13 -> 23.

Solution Approach:

The given problem can be solved with the help of a graph. We will follow the steps as:

1. We will do BFS as we need to find the minimum number of steps. Since there is no graph given the problem statement so we would create a graph with the help of prime number range from 1000 to 9999 as we need only 4 digits in the question.
2. To check prime number we will create a function isprime(x) which takes input as some variable x and return true if it is prime number otherwise false. We will store all the prime numbers in a vector and design a graph with them.
3. In the creation of the graph, we will check if the two prime numbers have only one digit which is not the same, So we create an isvalid(a,b) function that would return true and false if the combination is valid or not.
4. In each test case, we will initialize the dist of a node from parent node n to other connected nodes in a dist array with -1, and then we call bfs on n if the dist of node m in the graph remains -1 it means it has not been visited during bfs traversal, and we would print "Impossible".

Program to illustrate Prime path

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<ll> prime[100005]; //vector for adjacency list.
bool vis[100005]; //vis array to check if node is visited or not.
ll dist[100005]; //dist array to store dist of node.

//isprime function is used to check prime number or not.
bool isprime(ll x)
{
    //traverse from 2 to sqrt(x) and check divisibility.
    for (ll i = 2; i * i <= x; i++) {
        //if divisible then return false.
        if (x % i == 0)
            return false;
    }
    return true; //return true.
}
//isvalid() function is used to check if conversion is correct or not.
bool isvalid(ll a, ll b)
{
    ll cnt = 0; //initialise count variable to 0 for difference of digits.
    while (a > 0) {
        //if the digits value if not same then increment count.
        if (a % 10 != b % 10)
            cnt++;
        a /= 10; //reduce digit.
        b /= 10; //reduce digit.
    }
    if (cnt == 1)
        return true;
    else
        return false;
}
vector<ll> primes; //prime vector to store prime numbers.

//graph function to create a graph of prime number as its nodes.
void graph()
{
    //check number between 1000 to 9999 which are prime or not.
    for (ll i = 1000; i <= 9999; i++) {
        if (isprime(i)) //call isprime function.
            primes.push_back(i);
    }

    //create edges between prime numbers which are just one digit differ.
    for (ll i = 0; i < primes.size(); i++) {
        for (ll j = i + 1; j < primes.size(); j++) {
            ll a = primes[i];
            ll b = primes[j];
            if (isvalid(a, b)) //check validity.
            {
                //add edges between them.
                prime[a].push_back(b);
                prime[b].push_back(a);
            }
        }
    }
}

//define bfs function which takes single parameter as input.
void bfs(ll x)
{

    vis[x] = true; //make vis[x] as true.
    dist[x] = 0; //dist of current starting node is 0.
    queue<ll> q; //declare queue.
    q.push(x);
    //perform level order traversal.
    while (!q.empty()) {
        ll y = q.front();
        q.pop();
        for (ll i = 0; i < prime[y].size(); i++) {
            if (vis[prime[y][i]] == false) {
                q.push(prime[y][i]);
                //distance of child nodes are distance of parent plus one.
                dist[prime[y][i]] = dist[y] + 1;
                //push child into queue.
                vis[prime[y][i]] = true;
            }
        }
    }
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    graph(); //call graph function to create graph.
    while (t--) {
        cout << "Enter n and m: ";
        ll n, m;
        cin >> n >> m;

        for (ll i = 1000; i <= 9999; i++)
            //make all nodes unvisited initially and dist of each node as -1.
            dist[i] = -1, vis[i] = false;
        //call bfs for starting number n.
        bfs(n);

        //check if the node m distance is still -1 or not,
        //if -1 then we cant form m from n so print impossible
        //else print the steps.
        if (dist[m] != -1)
            cout << dist[m] << "\n";
        else
            cout << "Impossible"
                 << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter n and m: 1033 8179
6
Enter n and m: 1373 8017
7
Enter n and m: 1009 1009 
0

Problem source: PPATH - Prime Path