Min steps to convert N | Java program for the above problem ; Adjacency list for numbers till 100001 ; Visited array ; To store distance of every vertex from A ; Function to check if number is a prime ; Function to check if numbers differ by only a single - digit ; Check the last digit of both numbers and increase count if different ; Generate all N digit primes ; For every prime number i check if an edge can be made . ; For every prime number i check if an edge can be made from i to j . ; If edge is possible then insert in the adjacency list ; Function to count distance ; If unvisited push onto queue and mark visited as 1 and add the distance of curr + 1. ; Driver code ; Call bfs traversal with root as node A ; Indicates not possible
import java . util . * ; public class GFG { static Vector < Vector < Integer > > lis = new Vector < Vector < Integer > > ( ) ; static Vector < Integer > primes = new Vector < Integer > ( ) ; static int [ ] vis = new int [ 100001 ] ; static int [ ] dis = new int [ 100001 ] ; static boolean isPrime ( int n ) { int i = 2 ; while ( i * i <= n ) { if ( n % i == 0 ) return false ; i += 1 ; } return true ; } static boolean valid ( int a , int b ) { int c = 0 ; while ( a > 0 ) { if ( ( a % 10 ) != ( b % 10 ) ) c += 1 ; a = a / 10 ; b = b / 10 ; } if ( c == 1 ) return true ; else return false ; } static void makePrimes ( int N ) { int L = ( int ) Math . pow ( 10 , N - 1 ) ; int R = ( int ) Math . pow ( 10 , N ) - 1 ; for ( int i = L ; i < R + 1 ; i ++ ) { if ( isPrime ( i ) ) primes . add ( i ) ; } for ( int i = 0 ; i < primes . size ( ) ; i ++ ) { for ( int j = i + 1 ; j < primes . size ( ) ; j ++ ) { int a = primes . get ( i ) ; int b = primes . get ( j ) ; if ( valid ( a , b ) ) { lis . get ( a ) . add ( b ) ; lis . get ( b ) . add ( a ) ; } } } } static void bfs ( int src ) { Vector < Integer > q = new Vector < Integer > ( ) ; q . add ( src ) ; vis [ src ] = 1 ; dis [ src ] = 0 ; while ( q . size ( ) != 0 ) { int curr = q . get ( 0 ) ; q . remove ( 0 ) ; for ( int x : lis . get ( curr ) ) { if ( vis [ x ] == 0 ) { vis [ x ] = 1 ; q . add ( x ) ; dis [ x ] = dis [ curr ] + 1 ; } } } } public static void main ( String [ ] args ) { for ( int i = 0 ; i < 100001 ; i ++ ) { lis . add ( new Vector < Integer > ( ) ) ; } int N = 4 ; makePrimes ( N ) ; int A = 1033 ; int B = 8179 ; bfs ( A ) ; if ( dis [ B ] == - 1 ) { System . out . print ( - 1 ) ; } else { System . out . print ( dis [ B ] ) ; } } }