Count of N digit numbers which contains all single digit primes | Javascript program for the above approach ; Stores the index of prime numbers ; 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 . ; Initializing dp array with - 1. ; Indexing prime numbers in ascending order ; Given Input ; Function call
let dp = new Array ( 100 ) . fill ( 0 ) . map ( ( ) => new Array ( 1 << 4 ) ) ; let 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 ) { let countOfPrimes = countSetBits ( mask ) ; if ( countOfPrimes == 4 ) { return 1 ; } return 0 ; } let val = dp [ index ] [ mask ] ; if ( val != - 1 ) { return val ; } val = 0 ; if ( index == 1 ) { for ( let digit = N == 1 ? 0 : 1 ; digit <= 9 ; ++ digit ) { if ( primeIndex . has ( digit ) ) { let newMask = mask | ( 1 << primeIndex . get ( digit ) ) ; val += countOfNumbers ( index + 1 , newMask , N ) ; } else { val += countOfNumbers ( index + 1 , mask , N ) ; } } } else { for ( let digit = 0 ; digit <= 9 ; ++ digit ) { 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 val ; } for ( let i = 0 ; i < 100 ; i ++ ) { for ( let j = 0 ; j < 1 << 4 ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } primeIndex . set ( 2 , 0 ) ; primeIndex . set ( 3 , 1 ) ; primeIndex . set ( 5 , 2 ) ; primeIndex . set ( 7 , 3 ) ; let N = 4 ; document . write ( countOfNumbers ( 1 , 0 , N ) ) ;