Count of N digit numbers which contains all single-digit primes

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);
}

You can also try this code with Online C++ Compiler

Run Code

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: 

1. Initialise a global array, memo[1000][1 << 4] = -1. This is going to store the result of the subproblems. 
2. 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.  
3. 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. 

1. 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. 
2. We define a recursive function countValidNumbers(index, mask, n)  as follows:
   1. 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.
   2. 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.
   3. 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. 
   4. Finally, we return the value of ANS.

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;
}

You can also try this code with Online C++ Compiler

Run Code

Output: 

936

Complexity analysis 

Time complexity: O(N * 2⁴ * 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⁴) in number). Hence, the number of DP states is N * 2⁴. 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⁴)

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