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:

- 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.
- 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. - 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. - 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

Comments and Discussions!