Given a positive integer N, the task is to count the number of N-digit numbers which contain all single digit primes.
Examples:
Input: N = 4
Output: 24
Explanation: The number of single digit primes is 4 i.e.{2, 3, 5, 7}. Hence number of ways to arrange 4 numbers in 4 places is 4! = 24.Input: N = 5
Output: 936
Naive Approach: The simplest approach to solve the given problem is to generate all possible N-digit numbers and count those numbers which contain all single digit prime numbers. After checking for all the numbers, print the value of the count as the resultant total count of numbers.
Time Complexity: O(N *10N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by using Dynamic Programming because it has overlapping subproblems and optimal substructure. The subproblems can be stored in dp[][] table using memoization where dp[index][mask] stores the answer from the indexth position till the end, where mask is used to store the count of distinct primes included till now. Follow the steps below to solve the problem:
- Initialize a global multidimensional array dp[100][1<<4] with all values as -1 that stores the result of each recursive call.
- Index all the single digit prime numbers in ascending order using a HashMap.
- Define a recursive function, say countOfNumbers(index, mask, N) by performing the following steps.
- If the value of a index is equal to (N + 1),
- Count the number of distinct single digit primes included by finding the count of set bits in the mask.
- If the count is equal to 4, return 1 as a valid N-digit number has been formed.
- Otherwise return 0.
- If the result of the state dp[index][mask] is already computed, return this value dp[index][mask].
- If the current index is 1, then any digit from [1- 9] can be placed and if N = 1, then 0 can be placed as well.
- For all other index, any digit from [0-9] can be placed.
- If the current digit placed is a prime number, then set the index of the prime number to 1 in the bitmask.
- After making a valid placement, recursively call the countOfNumbers function for (index + 1).
- Return the sum of all possible valid placements of digits as the answer.
- If the value of a index is equal to (N + 1),
- Print the value returned by the function countOfNumbers(1, 0, N) as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Stores the dp-statesint dp[100][1 << 4];// Stores the index of prime numbersmap<int, int> primeIndex;int countOfNumbers(int index, int mask, int N){ // If index = N+1 if (index == N + 1) { // Find count of distinct // prime numbers by counting // number of set bits. int countOfPrimes = __builtin_popcount(mask); // If count of distinct // prime numbers is equal to 4 // return 1. if (countOfPrimes == 4) { return 1; } return 0; } int& val = dp[index][mask]; // If the state has // already been computed if (val != -1) { return val; } val = 0; // If current position is 1, // then any digit from [1-9] can be placed. // If N = 1, 0 can be also placed. if (index == 1) { for (int digit = (N == 1 ? 0 : 1); digit <= 9; ++digit) { // If the digit is a prime number, // set the index of the // digit to 1 in the bitmask. if (primeIndex.find(digit) != primeIndex.end()) { val += countOfNumbers( index + 1, mask | (1 << primeIndex[digit]), N); } else { val += countOfNumbers(index + 1, mask, N); } } } // For remaining positions, // any digit from [0-9] can be placed else { for (int digit = 0; digit <= 9; ++digit) { // If the digit is a prime number, // set the index of the // digit to 1 in the bitmask. if (primeIndex.find(digit) != primeIndex.end()) { val += countOfNumbers( index + 1, mask | (1 << primeIndex[digit]), N); } else { val += countOfNumbers(index + 1, mask, N); } } } // Return the answer. return val;}// Driver Codeint main(){ // Initializing dp array with -1. memset(dp, -1, sizeof dp); // Indexing prime numbers in // ascending order primeIndex[2] = 0; primeIndex[3] = 1; primeIndex[5] = 2; primeIndex[7] = 3; // Given Input int N = 4; // Function call. cout << countOfNumbers(1, 0, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{public static int[][] dp = new int[100][(1 << 4)];// Stores the index of prime numberspublic static HashMap<Integer, Integer> primeIndex = new HashMap<>();public static int countSetBits(int n){ int count = 0; while (n > 0) { count += n & 1; n >>= 1; } return count;}public static int countOfNumbers(int index, int mask, int N){ // If index = N+1 if (index == N + 1) { // Find count of distinct // prime numbers by counting // number of set bits. int countOfPrimes = countSetBits(mask); // If count of distinct // prime numbers is equal to 4 // return 1. if (countOfPrimes == 4) { return 1; } return 0; } int val = dp[index][mask]; // If the state has // already been computed if (val != -1) { return val; } val = 0; // If current position is 1, then any // digit from [1-9] can be placed. // If N = 1, 0 can be also placed. if (index == 1) { for(int digit = (N == 1 ? 0 : 1); digit <= 9; ++digit) { // If the digit is a prime number, // set the index of the digit to 1 // in the bitmask. if (primeIndex.containsKey(digit)) { int newMask = mask | (1 << primeIndex.get(digit)); val += countOfNumbers(index + 1, newMask, N); } else { val += countOfNumbers(index + 1, mask, N); } } } // For remaining positions, // any digit from [0-9] can be placed else { for(int digit = 0; digit <= 9; ++digit) { // If the digit is a prime number, // set the index of the digit to 1 // in the bitmask. if (primeIndex.containsKey(digit)) { int newMask = mask | (1 << primeIndex.get(digit)); val += countOfNumbers(index + 1, newMask, N); } else { val += countOfNumbers(index + 1, mask, N); } } } // Return the answer. return val;}// Driver Codepublic static void main(String[] args){ // Initializing dp array with -1. for(int i = 0; i < 100; i++) { for(int j = 0; j < (1 << 4); j++) { dp[i][j] = -1; } } // Indexing prime numbers in // ascending order primeIndex.put(2, 0); primeIndex.put(3, 1); primeIndex.put(5, 2); primeIndex.put(7, 3); // Given Input int N = 4; // Function call System.out.println(countOfNumbers(1, 0, N));}}// This code is contributed by maddler |
Python3
# Python3 program for the above approach# Stores the dp-statesdp = [[-1 for i in range(1<<4)] for j in range(100)]# Stores the index of prime numbersprimeIndex = {}def countSetBits(n): count = 0 while (n): count += n & 1 n >>= 1 return countdef countOfNumbers(index, mask, N): # If index = N+1 if (index == N + 1): # Find count of distinct # prime numbers by counting # number of set bits. countOfPrimes = countSetBits(mask); # If count of distinct # prime numbers is equal to 4 # return 1. if (countOfPrimes == 4): return 1 return 0 val = dp[index][mask] # If the state has # already been computed if (val != -1): return val val = 0 # If current position is 1, # then any digit from [1-9] can be placed. # If N = 1, 0 can be also placed. if (index == 1): digit = 0 if N == 1 else 1 while(digit <= 9): # If the digit is a prime number, # set the index of the # digit to 1 in the bitmask. if (digit in primeIndex): val += countOfNumbers(index + 1,mask | (1 << primeIndex[digit]), N) else: val += countOfNumbers(index + 1, mask, N) digit += 1 # For remaining positions, # any digit from [0-9] can be placed else: for digit in range(10): # If the digit is a prime number, # set the index of the # digit to 1 in the bitmask. if (digit in primeIndex): val += countOfNumbers(index + 1,mask | (1 << primeIndex[digit]), N) else: val += countOfNumbers(index + 1, mask, N) # Return the answer. return val# Driver Codeif __name__ == '__main__': # Initializing dp array with -1. # Indexing prime numbers in # ascending order primeIndex[2] = 0 primeIndex[3] = 1 primeIndex[5] = 2 primeIndex[7] = 3 # Given Input N = 4 # Function call. print(countOfNumbers(1, 0, N)) # This code is contributed by ipg2016107. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{public static int[,] dp = new int[100,(1 << 4)];// Stores the index of prime numberspublic static Dictionary<int,int> primeIndex = new Dictionary<int,int>();public static int countSetBits(int n){ int count = 0; while (n > 0) { count += n & 1; n >>= 1; } return count;}public static int countOfNumbers(int index, int mask, int N){ // If index = N+1 if (index == N + 1) { // Find count of distinct // prime numbers by counting // number of set bits. int countOfPrimes = countSetBits(mask); // If count of distinct // prime numbers is equal to 4 // return 1. if (countOfPrimes == 4) { return 1; } return 0; } int val = dp[index,mask]; // If the state has // already been computed if (val != -1) { return val; } val = 0; // If current position is 1, then any // digit from [1-9] can be placed. // If N = 1, 0 can be also placed. if (index == 1) { for(int digit = (N == 1 ? 0 : 1); digit <= 9; ++digit) { // If the digit is a prime number, // set the index of the digit to 1 // in the bitmask. if (primeIndex.ContainsKey(digit)) { int newMask = mask | (1 << primeIndex[digit]); val += countOfNumbers(index + 1, newMask, N); } else { val += countOfNumbers(index + 1, mask, N); } } } // For remaining positions, // any digit from [0-9] can be placed else { for(int digit = 0; digit <= 9; ++digit) { // If the digit is a prime number, // set the index of the digit to 1 // in the bitmask. if (primeIndex.ContainsKey(digit)) { int newMask = mask | (1 << primeIndex[digit]); val += countOfNumbers(index + 1, newMask, N); } else { val += countOfNumbers(index + 1, mask, N); } } } // Return the answer. return val;}// Driver Codepublic static void Main(String[] args){ // Initializing dp array with -1. for(int i = 0; i < 100; i++) { for(int j = 0; j < (1 << 4); j++) { dp[i,j] = -1; } } // Indexing prime numbers in // ascending order primeIndex.Add(2, 0); primeIndex.Add(3, 1); primeIndex.Add(5, 2); primeIndex.Add(7, 3); // Given Input int N = 4; // Function call Console.WriteLine(countOfNumbers(1, 0, N));}}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program for the above approachlet dp = new Array(100).fill(0).map(() => new Array(1 << 4));// Stores the index of prime numberslet primeIndex = new Map();function countSetBits(n) { let count = 0; while (n > 0) { count += n & 1; n >>= 1; } return count;}function countOfNumbers(index, mask, N) { // If index = N+1 if (index == N + 1) { // Find count of distinct // prime numbers by counting // number of set bits. let countOfPrimes = countSetBits(mask); // If count of distinct // prime numbers is equal to 4 // return 1. if (countOfPrimes == 4) { return 1; } return 0; } let val = dp[index][mask]; // If the state has // already been computed if (val != -1) { return val; } val = 0; // If current position is 1, then any // digit from [1-9] can be placed. // If N = 1, 0 can be also placed. if (index == 1) { for (let digit = N == 1 ? 0 : 1; digit <= 9; ++digit) { // If the digit is a prime number, // set the index of the digit to 1 // in the bitmask. if (primeIndex.has(digit)) { let newMask = mask | (1 << primeIndex.get(digit)); val += countOfNumbers(index + 1, newMask, N); } else { val += countOfNumbers(index + 1, mask, N); } } } // For remaining positions, // any digit from [0-9] can be placed else { for (let digit = 0; digit <= 9; ++digit) { // If the digit is a prime number, // set the index of the digit to 1 // in the bitmask. if (primeIndex.has(digit)) { let newMask = mask | (1 << primeIndex.get(digit)); val += countOfNumbers(index + 1, newMask, N); } else { val += countOfNumbers(index + 1, mask, N); } } } // Return the answer. return val;}// Driver Code// Initializing dp array with -1.for (let i = 0; i < 100; i++) { for (let j = 0; j < 1 << 4; j++) { dp[i][j] = -1; }}// Indexing prime numbers in// ascending orderprimeIndex.set(2, 0);primeIndex.set(3, 1);primeIndex.set(5, 2);primeIndex.set(7, 3);// Given Inputlet N = 4;// Function calldocument.write(countOfNumbers(1, 0, N));// This code is contributed by gfgking</script> |
Output
24
Time Complexity: O(N *10 * 24)
Auxiliary Space: O(N * 24)
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!
