Given two N-digit prime numbers A and B, the task is to find the minimum number of steps taken to convert A to B. Condition for the conversion is that only 1 digit of the current prime number can be modified such that the new number formed is also a prime number. If no such conversion is possible, print -1.
Note: The range of N is [1, 5].
Examples:
Input: N = 4, A = 1033, B = 8179
Output: 6
Explanation: The steps of conversion are 1033 -> 1733 -> 3733 -> 3739 -> 3779 -> 8779 -> 8179. While changing numbers from 1033->1733, they differ by only one digit and the same happens for subsequent steps.Input: N = 4, A = 1373, B = 8179
Output: 7Input: N = 2, A = 11, B = 37
Output: 2
Explanation: The steps of conversion are 11 -> 17 -> 37
Approach: Using Breadth First Search Algorithm
- Find all N digit prime numbers and make a graph with these numbers.
- Consider each prime number as a node of a graph and create an edge from one node to another if they differ by a single digit.
- Apply BFS traversal and find out the number of edges between A and B.
- If no path exists, print -1.
- Else print the no. of edges, which is the required solution.
Below is the implementation of the above approach.
C++
// C++ program for the above problem#include <bits/stdc++.h>using namespace std;#define ll long long#define mod 1000000007#define pb push_back#define mod 1000000007#define vi vector<int>// adjacency list for numbers// till 100001vi lis[100001];vi primes;// visited arrayint vis[100001];// to store distance of every// vertex from Aint dis[100001];// function to check if number// is a primebool isPrime(int n){ for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true;}// function to check if numbers// differ by only a single-digitbool valid(int a, int b){ int c = 0; while (a) { // check the last digit of // both numbers and increase // count if different 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; // generate all N digit primes for (int i = L; i <= R; i++) { if (isPrime(i)) { primes.pb(i); } } for (i = 0; i < primes.size(); i++) { // for every prime number i // check if an edge // can be made. for (j = i + 1; j < primes.size(); j++) { int a = primes[i]; int b = primes[j]; // for every prime number // i check if an edge can // be made from i to j. if (valid(a, b)) { // if edge is possible then // insert in the adjacency // list lis[a].pb(b); lis[b].pb(a); } } }}// function to count distancevoid 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 unvisited push onto queue // and mark visited as 1 and // add the distance of curr+1. if (vis[x] == 0) { vis[x] = 1; q.push(x); dis[x] = dis[curr] + 1; } } }}// Driver codeint main(){ int N = 4; makePrimes(N); int A = 1033, B = 8179; // Call bfs traversal // with root as node A bfs(A); if (dis[B] == -1) // Indicates not possible cout << "-1" << endl; else cout << dis[B] << endl; return 0;} |
Java
// Java program for the above problem import java.util.*;public class GFG{ // Adjacency list for numbers // till 100001 static Vector<Vector<Integer>> lis = new Vector<Vector<Integer>>(); static Vector<Integer> primes = new Vector<Integer>(); // Visited array static int[] vis = new int[100001]; // To store distance of every // vertex from A static int[] dis = new int[100001]; // Function to check if number // is a prime static boolean isPrime(int n) { int i = 2; while (i * i <= n) { if (n % i == 0) return false; i += 1; } return true; } // Function to check if numbers // differ by only a single-digit static boolean valid(int a, int b) { int c = 0; while(a > 0) { // Check the last digit of // both numbers and increase // count if different 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) { // Generate all N digit primes 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 every prime number i // check if an edge // can be made. for(int j = i + 1; j < primes.size(); j++) { int a = primes.get(i); int b = primes.get(j); // For every prime number // i check if an edge can // be made from i to j. if (valid(a, b)) { // If edge is possible then // insert in the adjacency // list lis.get(a).add(b); lis.get(b).add(a); } } } } // Function to count distance 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 unvisited push onto queue // and mark visited as 1 and // add the distance of curr+1. if (vis[x] == 0) { vis[x] = 1; q.add(x); dis[x] = dis[curr] + 1; } } } } // Driver code 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; // Call bfs traversal // with root as node A bfs(A); if (dis[B] == -1) { // Indicates not possible System.out.print(-1); } else { System.out.print(dis[B]); } }}// This code is contributed by divyesh072019 |
Python3
# Python3 program for the above problem mod = 1000000007# Adjacency list for numbers # till 100001 lis = [[] for i in range(100001)]primes = []# Visited arrayvis = [0 for i in range(100001)]# To store distance of every # vertex from A dis = [0 for i in range(100001)]# Function to check if number # is a primedef isPrime(n): i = 2 while (i * i <= n): if (n % i == 0): return False i += 1 return True# Function to check if numbers # differ by only a single-digitdef valid(a, b): c = 0 while(a): # Check the last digit of # both numbers and increase # count if different if ((a % 10) != (b % 10)): c += 1 a = int(a / 10) b = int(b / 10) if (c == 1): return True else: return Falsedef makePrimes(N): global primes global lis i = 0 j = 0 # Generate all N digit primes L = pow(10, N - 1) R = pow(10, N) - 1 for i in range(L, R + 1): if (isPrime(i)): primes.append(i) for i in range(len(primes)): # For every prime number i # check if an edge # can be made. for j in range(i + 1, len(primes)): a = primes[i] b = primes[j] # For every prime number # i check if an edge can # be made from i to j. if (valid(a, b)): # If edge is possible then # insert in the adjacency # list lis[a].append(b) lis[b].append(a)# Function to count distance def bfs(src): global vis global dis q = [] q.append(src) vis[src] = 1 dis[src] = 0 while (len(q) != 0): curr = q[0] q.pop(0) for x in lis[curr]: # If unvisited push onto queue # and mark visited as 1 and # add the distance of curr+1. if (vis[x] == 0): vis[x] = 1 q.append(x) dis[x] = dis[curr] + 1# Driver code N = 4makePrimes(N) A = 1033B = 8179# Call bfs traversal # with root as node A bfs(A)if (dis[B] == -1): # Indicates not possible print(-1)else: print(dis[B])# This code is contributed by avanitrachhadiya2155 |
C#
// C# program for the above problem using System;using System.Collections.Generic;class GFG { // Adjacency list for numbers // till 100001 static List<List<int>> lis = new List<List<int>>(); static List<int> primes = new List<int>(); // Visited array static int[] vis = new int[100001]; // To store distance of every // vertex from A static int[] dis = new int[100001]; // Function to check if number // is a prime static bool isPrime(int n) { int i = 2; while (i * i <= n) { if (n % i == 0) return false; i += 1; } return true; } // Function to check if numbers // differ by only a single-digit static bool valid(int a, int b) { int c = 0; while(a > 0) { // Check the last digit of // both numbers and increase // count if different 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) { // Generate all N digit primes 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 every prime number i // check if an edge // can be made. for(int j = i + 1; j < primes.Count; j++) { int a = primes[i]; int b = primes[j]; // For every prime number // i check if an edge can // be made from i to j. if (valid(a, b)) { // If edge is possible then // insert in the adjacency // list lis[a].Add(b); lis[b].Add(a); } } } } // Function to count distance 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 unvisited push onto queue // and mark visited as 1 and // add the distance of curr+1. if (vis[x] == 0) { vis[x] = 1; q.Add(x); dis[x] = dis[curr] + 1; } } } } // Driver code 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; // Call bfs traversal // with root as node A bfs(A); if (dis[B] == -1) { // Indicates not possible Console.Write(-1); } else { Console.Write(dis[B]); } }} |
Javascript
// JS program for the above problemlet mod = 1000000007// adjacency list for numbers// till 100001let lis = new Array(100001);for (var i = 0; i < 100001; i++) lis[i] = new Array(); let primes = [];// visited arraylet vis = new Array(100001).fill(0);// to store distance of every// vertex from Alet dis = new Array(100001).fill(0);// function to check if number// is a primefunction isPrime(n){ for (let i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true;}// function to check if numbers// differ by only a single-digitfunction valid(a, b){ let c = 0; while (a > 0) { // check the last digit of // both numbers and increase // count if different if ((a % 10) != (b % 10)) { c++; } a = Math.floor(a / 10); b = Math.floor(b / 10); } if (c == 1) { return true; } else { return false; }}function makePrimes( N){ let i, j; let L = 10 ** (N - 1); let R = (10 ** N) - 1; // generate all N digit primes for (i = L; i <= R; i++) { if (isPrime(i)) { primes.push(i); } } for (i = 0; i < primes.length; i++) { // for every prime number i // check if an edge // can be made. for (j = i + 1; j < primes.length; j++) { let a = primes[i]; let b = primes[j]; // for every prime number // i check if an edge can // be made from i to j. if (valid(a, b)) { //console.log(lis[a], lis[b]) // if edge is possible then // insert in the adjacency // list let l1 = lis[a] let l2 = lis[b] l1.push(b) l2.push(a) lis[a] = l1 lis[b] = l2; } } }}// function to count distancefunction bfs(src){ let q = []; q.push(src); vis[src] = 1; dis[src] = 0; while ( q.length > 0) { let curr = q[0]; q.shift(); for (let x of lis[curr]) { // if unvisited push onto queue // and mark visited as 1 and // add the distance of curr+1. if (vis[x] == 0) { vis[x] = 1; q.push(x); dis[x] = dis[curr] + 1; } } }}// Driver codelet N = 4;makePrimes(N);let A = 1033, B = 8179;// Call bfs traversal// with root as node Abfs(A);if (dis[B] == -1) // Indicates not possible console.log(-1)else console.log(dis[B]);// This code is contributed by phasing17. |
Output:
6
Time Complexity: O(102N)
Auxiliary Space Complexity: O(105)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
