Count N | C ++ program for the above approach ; Stores the dp - states ; Function to calculate the count of N - digit numbers that contains all digits from [ 0 - 9 ] atleast once ; If all digits are traversed ; Check if all digits are included in the mask ; If the state has already been computed ; If the current digit is 1 , any digit from [ 1 - 9 ] can be placed . If N == 1 , 0 can also be placed ; For other positions , any digit from [ 0 - 9 ] can be placed ; Return the answer ; Driver Code ; Initializing dp array with - 1. ; Given Input ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; long long dp [ 100 ] [ 1 << 10 ] ; long long countOfNumbers ( int digit , int mask , int N ) { if ( digit == N + 1 ) { if ( mask == ( 1 << 10 ) - 1 ) return 1 ; return 0 ; } long long & val = dp [ digit ] [ mask ] ; if ( val != -1 ) return val ; val = 0 ; if ( digit == 1 ) { for ( int i = ( N == 1 ? 0 : 1 ) ; i <= 9 ; ++ i ) { val += countOfNumbers ( digit + 1 , mask | ( 1 << i ) , N ) ; } } else { for ( int i = 0 ; i <= 9 ; ++ i ) { val += countOfNumbers ( digit + 1 , mask | ( 1 << i ) , N ) ; } } return val ; } int main ( ) { memset ( dp , -1 , sizeof dp ) ; int N = 10 ; cout << countOfNumbers ( 1 , 0 , N ) ; return 0 ; }