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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long NEW_LINE #define mod  1000000007 NEW_LINE #define pb  push_back NEW_LINE #define mod  1000000007 NEW_LINE #define vi  vector<int> NEW_LINE vi lis [ 100001 ] ; vi primes ; int vis [ 100001 ] ; int dis [ 100001 ] ; bool isPrime ( int n ) { for ( int i = 2 ; i * i <= n ; i ++ ) { if ( n % i == 0 ) return false ; } return true ; } bool valid ( int a , int b ) { int c = 0 ; while ( a ) { if ( ( a % 10 ) != ( b % 10 ) ) { c ++ ; } a = a / 10 ; b = b / 10 ; } if ( c == 1 ) { return true ; } else { return false ; } } void makePrimes ( int N ) { int i , j ; int L = pow ( 10 , N - 1 ) ; int R = pow ( 10 , N ) - 1 ; for ( int i = L ; i <= R ; i ++ ) { if ( isPrime ( i ) ) { primes . pb ( i ) ; } } for ( i = 0 ; i < primes . size ( ) ; i ++ ) { for ( j = i + 1 ; j < primes . size ( ) ; j ++ ) { int a = primes [ i ] ; int b = primes [ j ] ; if ( valid ( a , b ) ) { lis [ a ] . pb ( b ) ; lis [ b ] . pb ( a ) ; } } } } void bfs ( int src ) { queue < int > q ; q . push ( src ) ; vis [ src ] = 1 ; dis [ src ] = 0 ; while ( ! q . empty ( ) ) { int curr = q . front ( ) ; q . pop ( ) ; for ( int x : lis [ curr ] ) { if ( vis [ x ] == 0 ) { vis [ x ] = 1 ; q . push ( x ) ; dis [ x ] = dis [ curr ] + 1 ; } } } } int main ( ) { int N = 4 ; makePrimes ( N ) ; int A = 1033 , B = 8179 ; bfs ( A ) ; if ( dis [ B ] == -1 ) cout << " - 1" << endl ; else cout << dis [ B ] << endl ; return 0 ; }