Min steps to convert N | C # 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
using System ; using System . Collections . Generic ; class GFG { static List < List < int > > lis = new List < List < int > > ( ) ; static List < int > primes = new List < int > ( ) ; static int [ ] vis = new int [ 100001 ] ; static int [ ] dis = new int [ 100001 ] ; static bool isPrime ( int n ) { int i = 2 ; while ( i * i <= n ) { if ( n % i == 0 ) return false ; i += 1 ; } return true ; } static bool 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 . Count ; i ++ ) { for ( int j = i + 1 ; j < primes . Count ; j ++ ) { int a = primes [ i ] ; int b = primes [ j ] ; if ( valid ( a , b ) ) { lis [ a ] . Add ( b ) ; lis [ b ] . Add ( a ) ; } } } } static void bfs ( int src ) { List < int > q = new List < int > ( ) ; q . Add ( src ) ; vis [ src ] = 1 ; dis [ src ] = 0 ; while ( q . Count != 0 ) { int curr = q [ 0 ] ; q . RemoveAt ( 0 ) ; foreach ( int x in lis [ curr ] ) { if ( vis [ x ] == 0 ) { vis [ x ] = 1 ; q . Add ( x ) ; dis [ x ] = dis [ curr ] + 1 ; } } } } static void Main ( ) { for ( int i = 0 ; i < 100001 ; i ++ ) { lis . Add ( new List < int > ( ) ) ; } int N = 4 ; makePrimes ( N ) ; int A = 1033 ; int B = 8179 ; bfs ( A ) ; if ( dis [ B ] == - 1 ) { Console . Write ( - 1 ) ; } else { Console . Write ( dis [ B ] ) ; } } }