Count of N digit numbers which contains all single digit primes | C ++ program for the above approach ; Function ; If index = N + 1 ; Find count of distinct prime numbers by counting number of set bits . ; If count of distinct prime numbers is equal to 4 return 1. ; If the state has already been computed ; If current position is 1 , then any digit from [ 1 - 9 ] can be placed . If N = 1 , 0 can be also placed . ; If the digit is a prime number , set the index of the digit to 1 in the bitmask . ; For remaining positions , any digit from [ 0 - 9 ] can be placed ; If the digit is a prime number , set the index of the digit to 1 in the bitmask . ; Return the answer . ; Driver Code ; Initializing dp array with - 1. ; Indexing prime numbers in ascending order ; Given Input ; Function call .
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 100 ] [ 1 << 4 ] ; map < int , int > primeIndex ; int countOfNumbers ( int index , int mask , int N ) { if ( index == N + 1 ) { int countOfPrimes = __builtin_popcount ( mask ) ; if ( countOfPrimes == 4 ) { return 1 ; } return 0 ; } int & val = dp [ index ] [ mask ] ; if ( val != -1 ) { return val ; } val = 0 ; if ( index == 1 ) { for ( int digit = ( N == 1 ? 0 : 1 ) ; digit <= 9 ; ++ digit ) { if ( primeIndex . find ( digit ) != primeIndex . end ( ) ) { val += countOfNumbers ( index + 1 , mask | ( 1 << primeIndex [ digit ] ) , N ) ; } else { val += countOfNumbers ( index + 1 , mask , N ) ; } } } else { for ( int digit = 0 ; digit <= 9 ; ++ digit ) { if ( primeIndex . find ( digit ) != primeIndex . end ( ) ) { val += countOfNumbers ( index + 1 , mask | ( 1 << primeIndex [ digit ] ) , N ) ; } else { val += countOfNumbers ( index + 1 , mask , N ) ; } } } return val ; } int main ( ) { memset ( dp , -1 , sizeof dp ) ; primeIndex [ 2 ] = 0 ; primeIndex [ 3 ] = 1 ; primeIndex [ 5 ] = 2 ; primeIndex [ 7 ] = 3 ; int N = 4 ; cout << countOfNumbers ( 1 , 0 , N ) ; return 0 ; }