Min steps to convert N | Python3 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
mod = 1000000007 NEW_LINE lis = [ [ ] for i in range ( 100001 ) ] NEW_LINE primes = [ ] NEW_LINE vis = [ 0 for i in range ( 100001 ) ] NEW_LINE dis = [ 0 for i in range ( 100001 ) ] NEW_LINE def isPrime ( n ) : NEW_LINE INDENT i = 2 NEW_LINE while ( i * i <= n ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT i += 1 NEW_LINE DEDENT return True NEW_LINE DEDENT def valid ( a , b ) : NEW_LINE INDENT c = 0 NEW_LINE while ( a ) : NEW_LINE INDENT if ( ( a % 10 ) != ( b % 10 ) ) : NEW_LINE INDENT c += 1 NEW_LINE DEDENT a = int ( a / 10 ) NEW_LINE b = int ( b / 10 ) NEW_LINE DEDENT if ( c == 1 ) : NEW_LINE INDENT return True NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT def makePrimes ( N ) : NEW_LINE INDENT global primes NEW_LINE global lis NEW_LINE i = 0 NEW_LINE j = 0 NEW_LINE L = pow ( 10 , N - 1 ) NEW_LINE R = pow ( 10 , N ) - 1 NEW_LINE for i in range ( L , R + 1 ) : NEW_LINE INDENT if ( isPrime ( i ) ) : NEW_LINE INDENT primes . append ( i ) NEW_LINE DEDENT DEDENT for i in range ( len ( primes ) ) : NEW_LINE INDENT for j in range ( i + 1 , len ( primes ) ) : NEW_LINE INDENT a = primes [ i ] NEW_LINE b = primes [ j ] NEW_LINE if ( valid ( a , b ) ) : NEW_LINE INDENT lis [ a ] . append ( b ) NEW_LINE lis [ b ] . append ( a ) NEW_LINE DEDENT DEDENT DEDENT DEDENT def bfs ( src ) : NEW_LINE INDENT global vis NEW_LINE global dis NEW_LINE q = [ ] NEW_LINE q . append ( src ) NEW_LINE vis [ src ] = 1 NEW_LINE dis [ src ] = 0 NEW_LINE while ( len ( q ) != 0 ) : NEW_LINE INDENT curr = q [ 0 ] NEW_LINE q . pop ( 0 ) NEW_LINE for x in lis [ curr ] : NEW_LINE INDENT if ( vis [ x ] == 0 ) : NEW_LINE INDENT vis [ x ] = 1 NEW_LINE q . append ( x ) NEW_LINE dis [ x ] = dis [ curr ] + 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT N = 4 NEW_LINE makePrimes ( N ) NEW_LINE A = 1033 NEW_LINE B = 8179 NEW_LINE bfs ( A ) NEW_LINE if ( dis [ B ] == - 1 ) : NEW_LINE INDENT print ( - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( dis [ B ] ) NEW_LINE DEDENT