Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Example
2.
Solution approach
2.1.
Naive approach
2.2.
C++ Code 
2.3.
Output:
2.4.
Complexity Analysis:
2.5.
Efficient Approach
2.6.
Algorithm
2.7.
C++ Code
2.8.
Output: 
2.9.
Complexity analysis 
3.
FAQs
4.
Key Takeaways
Last Updated: Mar 27, 2024

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

Author Ayush Prakash
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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 * 10N

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 * 10N). 

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

Output: 

936

Complexity analysis 

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

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

FAQs

  1. What are the possible values of the bitmask(in this problem)? Explain.  
    The bitmask can take 16 values, from [0,15]. Since there are four single-digit prime numbers {2, 3, 5 and 7}, we require 4 bits to represent their presence or absence. If a bit is set i.e. “1”, this means that the digit is present if it is “0”, this means that the digit is not present. For example, 0000 = 0 would represent that none of them is present, 1111 = 15 would represent that all of them are present. 1010 = 10 would represent that 3 and 7 are present. The last bit (LSB) holds info for 2 and the first bit(MSB) holds info for 7.
     
  2. How many N-digit numbers are there? Explain. 
    There are 9 * 10(N-1) N-digit numbers in total. The first N-digit number is 10(N-1). The last N-digit number is 10N - 1. The total number of N-digit numbers = 10N - 1 - 10(N-1) + 1 = 9 * 10(N-1).

Key Takeaways

In this blog, we solved a digit DP problem. We discussed two approaches, a naive approach where we just iterated over every N-digit number and checked if it contains all single-digit primes. The time complexity was exponential in this case. We used memoization to optimise the solution and improved the time complexity to roughly O(N) in the efficient approach. In this approach, we used a technique called "masking", which is a very popular technique in competitive programming. 

If you love solving coding problems, please visit this incredible platform Coding Ninjas Studio.

If you feel that this blog has helped you in any way, then please do share it with your friends. Happy Coding!

Live masterclass