Solution
This problem can be solved using Breadth First Search(BFS) Technique.
Algorithm
-
We will find out all 4-digit prime numbers till 9999.
-
Using the numbers found in the above step, form the graph using Adjacency List.
- After forming the adjacency list, we will simply apply the BFS.
Code Implementation
C++
/*C++ program find the shortest path to reach one
prime to other by changing single digit at a time.*/
#include <bits/stdc++.h>
using namespace std;
class Graph
{
int node;
list<int> *lst;
public:
Graph(int node)
{
this->node = node;
lst = new list<int>[node];
}
void insertedge(int node1, int node2)
{
lst[node1].push_back(node2);
lst[node2].push_back(node1);
}
int bfs(int in1, int in2);
};
/* Function to find all 4 digit prime numbers*/
void Sieve(vector<int> &v)
{
/*Form a boolean array and initialize*/
int N = 9999;
bool PrimeBool[N + 1];
memset(PrimeBool, true, sizeof(PrimeBool));
for (int l = 2; l * l <= N; l++)
{
/*If PrimeBool[l] is not changed, then it is a Prime*/
if (PrimeBool[l] == true)
{
/*Change all multiples of l*/
for (int i = l * l; i <= N; i += l)
PrimeBool[i] = false;
}
}
/* Making a vector of Prime numbers*/
for (int l = 1000; l <= N; l++)
if (PrimeBool[l])
v.push_back(l);
}
/* in1 and in2 are two vertices of Graph*/
int Graph::bfs(int in1, int in2)
{
int vis[node];
memset(vis, 0, sizeof(vis));
queue<int> q;
vis[in1] = 1;
q.push(in1);
list<int>::iterator i;
while (!q.empty())
{
int p = q.front();
q.pop();
for (i = lst[p].begin(); i != lst[p].end(); i++)
{
if (!vis[*i])
{
vis[*i] = vis[p] + 1;
q.push(*i);
}
if (*i == in2)
{
return vis[*i] - 1;
}
}
}
return 0;
}
/* Returns true if num1 and num2 differ by single digit.*/
bool Compare(int num1, int num2)
{
// To Compare the digits
string str1 = to_string(num1);
string str2 = to_string(num2);
int cal = 0;
if (str1[0] != str2[0])
cal++;
if (str1[1] != str2[1])
cal++;
if (str1[2] != str2[2])
cal++;
if (str1[3] != str2[3])
cal++;
return (cal == 1);
}
int ShortestPath(int num1, int num2)
{
// Generate all 4 digit
vector<int> pst;
Sieve(pst);
/*Create a Graph where node numbers are indexes
in pst[] and there is an edge between two
nodes only if they differ by single digit.*/
Graph g(pst.size());
for (int i = 0; i < pst.size(); i++)
for (int j = i + 1; j < pst.size(); j++)
if (Compare(pst[i], pst[j]))
g.insertedge(i, j);
int in1, in2;
for (int j = 0; j < pst.size(); j++)
if (pst[j] == num1)
in1 = j;
for (int j = 0; j < pst.size(); j++)
if (pst[j] == num2)
in2 = j;
return g.bfs(in1, in2);
}
// Main Code
int main()
{
int num1 = 1033, num2 = 8179;
cout << ShortestPath(num1, num2)<<endl;
return 0;
}
Time Complexity: O(N^2), since we are using BFS traversal for each iteration.
Space Complexity: O(N+E), where N is the number of nodes and E is the number of edges.
Also see, Euclid GCD Algorithm
Frequently Asked Questions
What is a Graph?
A graph is a non-linear data structure consisting of nodes and edges. In a graph, the edges are the lines or arcs that link any two nodes, and the nodes are sometimes referred to as vertices.
What is an Undirected Graph?
Undirected graphs have edges that do not have a direction. Each edge may be traversed in both directions, which indicates a two-way connection.
What is a Directed Graph?
A directed graph is one where all the edges are directed from one vertex to another. There is only a one-way connection between vertices.
What is a Prime Number?
A prime number is a natural number that is greater than one and is not the sum of two other natural numbers.
What is BFS Algorithm?
A breadth-first search(BFS) algorithm searches a tree data structure for nodes that satisfy a specific property. It starts at the root of the tree and traverses all nodes at the current depth before moving on to nodes at the next depth level.
Conclusion
In this article, we have solved the problem of finding the shortest path from one prime to the next by changing one digit at a time. I hope you enjoyed this blog on finding the shortest path from one prime to the next by changing one digit at a time.
Check out this problem - Root To Leaf Path
If you want to learn more, check out our articles on Minimum weight cycle in an undirected graph, Construct the Full K-ary Tree from its Preorder Traversal, Regular and Bipartite graphs, and Planar and Non-Planar Graphs.
Happy Coding!
38+ registered 