**Introduction**

Let us understand the problem statement first. We are given a positive integer 'N', and we need to calculate the total number of N-digit numbers that have all single-digit __primes__, i.e. {2, 3, 5, 7}.

**Example**

**Input**

`N = 4`

**Output**

`24`

**Explanation**:

Any permutation of {2, 3, 5, 7} will be counted in our answer. Hence our answer = 4! = 24.

**Input**

`N = 5`

**Output**

`936`

**Explanation**

The total number of five-digit numbers that include 2, 3, 5 and 7 is 936. We will not count it manually but verify it later in this blog.

**Solution approach**

**Naive approach**

- We will iterate over every n-digit number and check whether it contains all single-digit primes or not.
- We will maintain a 'COUNT', which is initialised to 0. Whenever a number contains all the single-digit primes, we will increment COUNT by 1.
- We will print COUNT as our final answer.

**C++ Code **

```
#include <bits/stdc++.h>
using namespace std;
bool check(int num)
{
/*
In this function, we iterate over
the digits of num and if the
digit is prime; we insert it
into the set 'temp.'
*/
set<int> temp;
while (num)
{
int digit = num % 10;
if (digit == 2 or digit == 3 or digit == 5 or digit == 7)
{
temp.insert(digit);
}
num /= 10;
}
/*
We check if temp's size is 4
This means that num contains all single-digit
primes i.e. 2,3,5,7
*/
return temp.size() == 4;
}
int countValidNumbers(int n)
{
// For n = 5, start = 10000, end = 99999
int start = pow(10, n - 1);
int end = pow(10, n) - 1;
int count = 0;
/*
Iterating over every number in the range
and checking if it includes all
single-digit primes
*/
for (int num = start; num <= end; num++)
{
if (check(num))
{
count++;
}
}
return count;
}
// Driver code
int main()
{
int n = 5;
cout << countValidNumbers(n);
}
```

**Output:**

`936`

**Complexity Analysis:**

**Time complexity: O(N * 10 ^{N}) **

There are 9 * 10^{(N-1)}, N-digit numbers (you can check yourself, it is basic maths). We are iterating over every N-digit number, and for every number, we are iterating over its digit to check whether it contains all single-digit primes or not. Hence the overall time complexity is O(N * 10^{N}).

**Space complexity: O(1)**

We are not using any extra space. Hence the overall space complexity is O(1).

**Efficient Approach**

We will solve this problem efficiently using dynamic programming since this problem has __optimal substructure and overlapping subproblems__. This is shown in the figure below.

The value of F(1,0,5) is derived from the subproblems (optimal substructure), and there are overlapping subproblems underlined in green and blue.

**F(1,0,5)** is the total number of 5 digit numbers with all single-digit primes. In actual code, we have used the function "**countValidNumbers**" instead of **F**, so don't get confused. We will understand what this function does in brief in the next section.

**Algorithm**

If the value of n < 4, we print 0 and exit. Because it is not possible to form a number with a count of digits < 4 and include all the single-digit primes {2, 3, 5, 7}, else we do this:

- Initialise a global array, memo[1000][1 << 4] = -1. This is going to store the result of the subproblems.
- Initialise a global map “
**primeMask**” as: primeMask[2] = 1 (0001), primeMask[3] = 2(0010), primeMask[5] = 4,(0100) primeMask[7] = 8(1000). This is going to update the value of the mask whenever the digit in process is prime. For example, if the digit in process is 3, we will update the**mask**as mask = mask | primeMask[3]. So, if initially, the mask is 0 (0000) in binary, it will now be updated to 0 OR 2 i.e. 0000 | 0010 = 0010. This represents that 3 is present in the number we are forming. - Since the number of single-digit prime numbers is four, the size of the mask is 4 bits, where a set bit represents the presence of 2, 3, 5, or 7. The lowest significant bit set represents the presence of 2, and the most significant bit represents the presence of 7. The image below will give you a more clear picture of the explanation above.

- Let us define our DP state. Memo[index][mask] stores the answer from the
**index**position till the end, where a**mask**is used to keep track of what all single-digit primes are included until now. The value of the**mask**can range from 0 to 15, 0 which is represented in binary as**0000**, means that none of the single-digit primes, i.e. 2,3,5 or 7 is included, whereas 15, which is represented as**1111**in binary, means all of the single-digit primes are included. -
We define a recursive function
**countValidNumbers(index, mask, n)**as follows:- The base case occurs when the
**index is equal to n + 1.**If the number of set bits in the mask = 4, return one else, return 0. - If the value of
**memo[index][mask]**is already calculated that is, its value is not equal to -1, return memo[index][mask]. Else initialize a variable**ANS = 0**. **If**the**index is 1**, then any digit from [1-9] can be placed. For all other indexes, any digit from [0-9] can be placed. If the digit is a**non-prime,**we recursively call for**countValidNumbers(index + 1, mask, n)**and add its value to ANS. If the digit is a prime {2, 3, 5, 7} we recursively call for**countValidNumbers(index + 1, mask | primeMask[digit], n)**and add its value to the**ANS.**Note here we updated the value of**the mask**by taking OR of the mask with primeMask[digit]**,**which essentially marks the presence of that prime digit.- Finally, we return the value of ANS.

- The base case occurs when the

**C++ Code**

```
#include <bits/stdc++.h>
using namespace std;
// Global variables declaration
int memo[1000][1 << 4];
map<int, int> primeMask;
int countValidNumbers(int index, int mask, int n)
{
// Base case
if (index == n + 1)
{
if (__builtin_popcount(mask) == 4)
{
return 1;
}
return 0;
}
/*
If we already have calculated the answer for the
subproblem then simply return the value of DP[index][mask]
*/
if (memo[index][mask] != -1)
{
return memo[index][mask];
}
int ans = 0;
/*
Placing digit [0-9] at the index when index > 1 else
placing digit [1-9].
*/
for (int digit = (index == 1 ? 1 : 0); digit <= 9; digit++)
{
/*
When a digit is a prime {2,3,5,7}, we update the value of the
mask by taking its OR with primeMask[digit], which essentially
marks the presence of that prime digit in the number. We then
recur for the next index. Otherwise, we simply recur for the
next index without changing the value of the mask.
*/
if (primeMask.find(digit) != primeMask.end())
{
ans += countValidNumbers(index + 1, mask | primeMask[digit], n);
}
else
{
ans += countValidNumbers(index + 1, mask, n);
}
}
return ans;
}
int main()
{
int n = 5;
/*
It is not possible for a number having the number
of digits < 4 to include all single-digit primes
that is 2,3,5 and 7, so we print 0 and exit.
*/
if (n < 4)
{
cout << 0;
return 0;
}
memset(memo, -1, sizeof(memo));
primeMask[2] = 1, primeMask[3] = 2, primeMask[5] = 4, primeMask[7] = 8;
int ans = countValidNumbers(1, 0, n);
cout << ans;
return 0;
}
```

**Output: **

936

**Complexity analysis **

**Time complexity: O(N * 2 ^{4} * 10)**

A DP state is defined using two variables, index and mask. The index can range from 1 to N, while the mask can range from 0-15 (that is 16 (2^{4}) in number). Hence, the number of DP states is **N * 2 ^{4}**. For a DP state that is yet to be calculated, we need to iterate through all the digits (0 - 9); hence the factor of 10 comes in the time complexity.

**Space complexity: O(N * 2 ^{4})**

We need an array of size N * 2^{4} to store the answers to the subproblems (DP states) so that we can use them instead of calculating again.