Shortest Prime Path in C++

By Anirudh C V

Find the distance of the shortest path from Num1 to Num2 that can be attained by altering only single digit at a time in C++

We find the distance of the Shortest Path from number 1 to number 2 that can be attained by altering only single digit at a time such that every number that we get after changing a digit is a four digit prime number with no leading zeros by the concept of BFS where number 1 and number 2 both are four digit prime numbers. 

Example 1 :

INPUT:

number 1-1249

number 2-1097

OUTPUT:

4  -  here all four digits 

 

Example 2 :

INPUT:

number 1-1523

number 2-1423

OUTPUT:

1