Count All Prime Numbers that Can be Formed using Digits of a Given Number

Approach

The idea is to generate all the permutations using recursion and backtracking and checking each of them whether it satisfies the given constraint or not.

Steps To Solve

• Initialize a hashmap 'mp' to avoid duplicates.
• Declare a variable 'ans' to store the count. 
• Make a function bool check(string &s) to check whether the number formed by the string s is valid or not. 
  • If the size of s is zero, return false.
  • Convert string s to integer using the inbuilt stoi function and store the integer in num.
  • If mp[num] == 1, it is already processed, return false. Else mark mp[num] as true. 
  • If num == 1, it is not a prime number, return false.
  • If num == 2, it is a prime, return true.
  • If num%2 == 0, it is not a prime, return false.
  • As 2 is only the even prime, and we have already checked for that, iterate to all the odd numbers 'i' over a range [3, N^(1/2)] and check if i is a factor of num or not, if yes return false.
  • If num passes all the above conditions, then it is a prime number that is not yet processed, so return true.
• Make a function void solve(string &s, string &curr, vector <bool> &vis, int &N) to generate all possible permutations.
  • Check whether the current string 'curr' is valid or not by calling check(curr). If it returns true, increment the answer by 1.
  •  Iterate over a range [0, N], using the variable i, and perform the following steps - 
  • Check whether the ith character of string s is included in the current string curr or not (vis[i] == true or false).
  • If vis[i] == false, mark it as true and push s[i] into curr.
  • Recursively call the function solve(s, curr, vis, N).
  • Backtrack to generate all the possible strings. 
• Call the function solve by passing the parameters (s, curr, vis, N).
• Print the answer.

Code       

#include <bits/stdc++.h>
using namespace std;
const int M = 1e2 + 7;
//hashmap avoid duplicates
unordered_map <int, int> mp;
//to store the answer
int ans;
//function to check whether the number formed by the string s is valid or not.
bool check(string &s){
   
   //If the size of s is zero
   if(s.size() == 0)
       return false;
   //Convert string s to integer
   int num = stoi(s);
   if(mp[num])
       //already processed
       return false;
   //mark num as processed
   mp[num] = true;
   //1 is not a prime
   if(num == 1)
       return false;
   //2 is a prime number
   if(num == 2)
       return true;
   //2 is a factor
   if(num%2 == 0)
       return false;
   //iterate to all the odd numbers 'i' over a range [3, N^(1/2)] and check if i is a factor of num or not
   for(int i = 3; i * i <= num; i += 2){
       if(num%i == 0)
           return false;
   }
   //num is a prime number
   return true;
}
// function to generate all possible permutations
void solve(string &s, string &curr, vector <bool> &vis, int &N){ 
   //check current string
   if(check(curr)){
       //increment answer by 1
       ++ans;
   }
   for(int i = 0; i < N; ++i){
       //Check whether the ith character of string s is included in the current string curr or not
       if(vis[i])
           continue;
       //mark i visited
       vis[i] = true;
       //puch character s[i] to curr
       curr.push_back(s[i]);
       solve(s, curr, vis, N);
       //backtrack
       curr.pop_back();
       vis[i] = false;
   }
}
signed main(){
   string s;
   cin >> s;
   int N = s.size();
   vector <bool> vis(N, 0);
   string curr = "";
   //function call
   solve(s, curr, vis, N);
   //print the answer
   cout << ans << "\n";
   return 0;
}

Input 

12345

Output

36

Complexities

Time Complexity

The time complexity is O(9^N)

Space Complexity

The space complexity is O(N) (ignoring the stack frames).

FAQs

1. What is Backtracking?
   Backtracking is an algorithmic tool that recursively generates all the possible combinations to solve the given problem.
    
2. How do you check if a number is prime or not efficiently?
   Checkout this coding ninja’s blog to get a better understanding.

Key Takeaways

In this article, we solved a problem using recursion and backtracking. If you want to master competitive programming or prepare for coding interviews, then backtracking is one of the most important topics. Check out this coding ninjas' blog for getting a better hold on it.

Also read, Permutation of string

To learn more about such data structures and algorithms, Coding Ninjas Studio is a one-stop destination. This platform will help you to improve your coding techniques and give you an overview of interview experiences in various product-based companies by providing Online Mock Test Series and many more benefits.

Happy learning!