1.
Introduction
2.
Problem Statement
3.
Solution
3.1.
Algorithm
3.2.
Code Implementation
4.
4.1.
What is a Graph?
4.2.
What is an Undirected Graph?
4.3.
What is a Directed Graph?
4.4.
What is a Prime Number?
4.5.
What is BFS Algorithm?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Find the Shortest Path From One Prime to the Next by Changing One Digit at a Time

Rajat Agrawal
1 upvote

## Introduction

A prime number is a natural number that is greater than one and is not the sum of two other natural numbers. For example, the number 7 is prime because there are only two ways to write it as a product, 1 × 7 and 7 × 1, involving 7 itself.

The prime numbers from 1 to 20 are 2, 3, 5, 7, 11, 13, 17, and 19.

In this blog, we will discuss the problem to find the shortest path from one prime to the next by changing one digit at a time.

## Problem Statement

Given two four-digit prime numbers, let's say 1033 and 8179, identify the shortest path from 1033 to 8179 by changing only one digit at a time so that every number we get after changing a digit is prime. For example, the answer is 1033, 1733, 3733, 3739, 3779, 8779, and 8179.

Examples:

Input: 1033 8179

Output: 6

Input: 1055 1055

Output: 0

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

### 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 graphConstruct the Full K-ary Tree from its Preorder TraversalRegular and Bipartite graphs, and Planar and Non-Planar Graphs.

Happy Coding!

Live masterclass