Count N-digit numbers that contains every possible digit atleast once
Given a positive integer N, the task is to count the number of N-digit numbers such that every digit from [0-9] occurs at least once.
Examples :
Input: N = 10
Output : 3265920Input: N = 5
Output: 0
Explanation: Since the number of digits is less than the minimum number of digits required [0-9], the answer is 0.
Naive Approach: The simplest approach to solve the problem is to generate over all possible N-digit numbers and for each such number, check if all its digits satisfy the required condition or not.
Time Complexity: O(10N*N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use Dynamic Programming as it has overlapping subproblems and optimal substructure. The subproblems can be stored in dp[][] table using memoization, where dp[digit][mask] stores the answer from the digitth position till the end, when the included digits are represented using a mask.
Follow the steps below to solve this problem:
- Define a recursive function, say countOfNumbers(digit, mask), and perform the following steps:
- Base Case: If the value of digit is equal to N+1, then check if the value of the mask is equal to (1 << 10 – 1). If found to be true, return 1 as a valid N-digit number is formed.
- If the result of the state dp[digit][mask] is already computed, return this state dp[digit][mask].
- If the current position is 1, then any digit from [1-9] can be placed. If N is equal to 1, then 0 can be placed as well.
- For any other position, any digit from [0-9] can be placed.
- If a particular digit ‘i’ is included, then update mask as mask = mask | (1 << i ).
- After making a valid placement, recursively call the countOfNumbers function for index digit+1.
- Return the sum of all possible valid placements of digits as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Stores the dp-states long long dp[100][1 << 10]; // Function to calculate the count of // N-digit numbers that contains all // digits from [0-9] atleast once long long countOfNumbers( int digit, int mask, int N) { // If all digits are traversed if (digit == N + 1) { // Check if all digits are // included in the mask if (mask == (1 << 10) - 1) return 1; return 0; } long long & val = dp[digit][mask]; // If the state has // already been computed if (val != -1) return val; val = 0; // If the current digit is 1, any // digit from [1-9] can be placed. // If N==1, 0 can also be placed if (digit == 1) { for ( int i = (N == 1 ? 0 : 1); i <= 9; ++i) { val += countOfNumbers(digit + 1, mask | (1 << i), N); } } // For other positions, any digit // from [0-9] can be placed else { for ( int i = 0; i <= 9; ++i) { val += countOfNumbers(digit + 1, mask | (1 << i), N); } } // Return the answer return val; } // Driver Code int main() { // Initializing dp array with -1. memset (dp, -1, sizeof dp); // Given Input int N = 10; // Function Call cout << countOfNumbers(1, 0, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Stores the dp-states static int dp[][] = new int [ 100 ][ 1 << 10 ]; // Function to calculate the count of // N-digit numbers that contains all // digits from [0-9] atleast once static long countOfNumbers( int digit, int mask, int N) { // If all digits are traversed if (digit == N + 1 ) { // Check if all digits are // included in the mask if (mask == ( 1 << 10 ) - 1 ) return 1 ; return 0 ; } long val = dp[digit][mask]; // If the state has // already been computed if (val != - 1 ) return val; val = 0 ; // If the current digit is 1, any // digit from [1-9] can be placed. // If N==1, 0 can also be placed if (digit == 1 ) { for ( int i = (N == 1 ? 0 : 1 ); i <= 9 ; ++i) { val += countOfNumbers(digit + 1 , mask | ( 1 << i), N); } } // For other positions, any digit // from [0-9] can be placed else { for ( int i = 0 ; i <= 9 ; ++i) { val += countOfNumbers(digit + 1 , mask | ( 1 << i), N); } } // Return the answer return val; } // Driver Code public static void main(String[] args) { // Initializing dp array with -1. for ( int i = 0 ;i<dp.length;i++) Arrays.fill(dp[i], - 1 ); // Given Input int N = 10 ; // Function Call System.out.print(countOfNumbers( 1 , 0 , N)); } } // This code is contributed by Rajput-Ji |
Python3
# Python program for the above approach # Stores the dp-states dp = [[ - 1 for j in range ( 1 << 10 )] for i in range ( 100 )] # Function to calculate the count of # N-digit numbers that contains all # digits from [0-9] atleast once def countOfNumbers(digit, mask, N): # If all digits are traversed if (digit = = N + 1 ): # Check if all digits are # included in the mask if (mask = = ( 1 << 10 ) - 1 ): return 1 return 0 val = dp[digit][mask] # If the state has # already been computed if (val ! = - 1 ): return val val = 0 # If the current digit is 1, any # digit from [1-9] can be placed. # If N==1, 0 can also be placed if (digit = = 1 ): for i in range (( 0 if (N = = 1 ) else 1 ), 10 ): val + = countOfNumbers(digit + 1 , mask | ( 1 << i), N) # For other positions, any digit # from [0-9] can be placed else : for i in range ( 10 ): val + = countOfNumbers(digit + 1 , mask | ( 1 << i), N) # Return the answer return val # Driver Code # Given Input N = 10 # Function Call print (countOfNumbers( 1 , 0 , N)) # This code is contributed by shinjanpatra |
C#
// C# program to implement above approach using System; using System.Collections.Generic; class GFG { // Stores the dp-states static long [][] dp = new long [100][]; // Function to calculate the count of // N-digit numbers that contains all // digits from [0-9] atleast once static long countOfNumbers( int digit, int mask, int N) { // If all digits are traversed if (digit == N + 1) { // Check if all digits are // included in the mask if (mask == (1 << 10) - 1){ return 1; } return 0; } long val = dp[digit][mask]; // If the state has // already been computed if (val != -1){ return val; } val = 0; // If the current digit is 1, any // digit from [1-9] can be placed. // If N==1, 0 can also be placed if (digit == 1) { for ( int i = (N == 1 ? 0 : 1) ; i <= 9 ; ++i) { val += countOfNumbers(digit + 1, mask | (1 << i), N); } } // For other positions, any digit // from [0-9] can be placed else { for ( int i = 0; i <= 9; ++i) { val += countOfNumbers(digit + 1, mask | (1 << i), N); } } dp[digit][mask] = val; // Return the answer return val; } // Driver Code public static void Main( string [] args){ // Initializing dp array with -1. for ( int i = 0 ; i < dp.Length ; i++){ dp[i] = new long [1 << 10]; for ( int j = 0 ; j < (1 << 10) ; j++){ dp[i][j] = -1; } } // Given Input int N = 10; // Function Call Console.Write(countOfNumbers(1, 0, N)); } } // This code is contributed by subhamgoyal2014. |
Javascript
<script> // JavaScript program for the above approach // Stores the dp-states let dp = new Array(100); for (let i = 0; i < 100; i++) { dp[i] = new Array(1 << 10).fill(-1); } // Function to calculate the count of // N-digit numbers that contains all // digits from [0-9] atleast once function countOfNumbers(digit, mask, N) { // If all digits are traversed if (digit == N + 1) { // Check if all digits are // included in the mask if (mask == (1 << 10) - 1) return 1; return 0; } let val = dp[digit][mask]; // If the state has // already been computed if (val != -1) return val; val = 0; // If the current digit is 1, any // digit from [1-9] can be placed. // If N==1, 0 can also be placed if (digit == 1) { for (let i = (N == 1 ? 0 : 1); i <= 9; ++i) { val += countOfNumbers(digit + 1, mask | (1 << i), N); } } // For other positions, any digit // from [0-9] can be placed else { for (let i = 0; i <= 9; ++i) { val += countOfNumbers(digit + 1, mask | (1 << i), N); } } // Return the answer return val; } // Driver Code // Given Input let N = 10; // Function Call document.write(countOfNumbers(1, 0, N)); </script> |
3265920
Time Complexity: O(N2*210)
Auxiliary Space: O(N*210)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a DP to store the solution of the subproblems and initialize it with 0.\
- Initialize the DP with base cases dp[0][0] = 1.
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP
- Create a variable ans to store final result and iterate over DP and update ans.
- Return the final solution stored in ans.
Implementation :
C++
#include <bits/stdc++.h> using namespace std; // Function to calculate the count of // N-digit numbers that contains all // digits from [0-9] atleast once long long countOfNumbers( int N) { // Stores the dp-states long long dp[N + 1][1 << 10]; // Initializing dp array with 0 memset (dp, 0, sizeof (dp)); // Setting initial state dp[0][0] = 1; // Computing DP table for ( int digit = 1; digit <= N; ++digit) { // If the current digit is 1, any // digit from [1-9] can be placed. // If N==1, 0 can also be placed if (digit == 1) { for ( int i = (N == 1 ? 0 : 1); i <= 9; ++i) { for ( int mask = 0; mask < (1 << 10); ++mask) { dp[digit][mask | (1 << i)] += dp[digit - 1][mask]; } } } // For other positions, any digit // from [0-9] can be placed else { for ( int i = 0; i <= 9; ++i) { for ( int mask = 0; mask < (1 << 10); ++mask) { dp[digit][mask | (1 << i)] += dp[digit - 1][mask]; } } } } // Check if all digits are // included in the mask long long ans = 0; for ( int mask = 0; mask < (1 << 10); ++mask) { if (mask == (1 << 10) - 1) ans += dp[N][mask]; } // Return the answer return ans; } // Driver Code int main() { // Given Input int N = 10; // Function Call cout << countOfNumbers(N); return 0; } // --- by bhardwajji |
Java
import java.util.Arrays; public class GFG { // Function to calculate the count of N-digit numbers that contain all digits from [0-9] at least once static long countOfNumbers( int N) { // Stores the dp-states long [][] dp = new long [N + 1 ][ 1 << 10 ]; // Initializing dp array with 0 for ( long [] row : dp) { Arrays.fill(row, 0 ); } // Setting initial state dp[ 0 ][ 0 ] = 1 ; // Computing DP table for ( int digit = 1 ; digit <= N; ++digit) { // If the current digit is 1, any digit from [1-9] can be placed. // If N==1, 0 can also be placed if (digit == 1 ) { for ( int i = (N == 1 ? 0 : 1 ); i <= 9 ; ++i) { for ( int mask = 0 ; mask < ( 1 << 10 ); ++mask) { dp[digit][mask | ( 1 << i)] += dp[digit - 1 ][mask]; } } } // For other positions, any digit from [0-9] can be placed else { for ( int i = 0 ; i <= 9 ; ++i) { for ( int mask = 0 ; mask < ( 1 << 10 ); ++mask) { dp[digit][mask | ( 1 << i)] += dp[digit - 1 ][mask]; } } } } // Check if all digits are included in the mask long ans = 0 ; for ( int mask = 0 ; mask < ( 1 << 10 ); ++mask) { if (mask == ( 1 << 10 ) - 1 ) { ans += dp[N][mask]; } } // Return the answer return ans; } // Driver Code public static void main(String[] args) { // Given Input int N = 10 ; // Function Call System.out.println(countOfNumbers(N)); // This Code is Contributed by Shivam Tiwari } } |
Python
# Function to calculate the count of # N-digit numbers that contains all # digits from [0-9] atleast once def countOfNumbers(N): # Stores the dp-states dp = [[ 0 ] * ( 1 << 10 ) for i in range (N + 1 )] # Initializing dp array with 0 for i in range (N + 1 ): for j in range ( 1 << 10 ): dp[i][j] = 0 # Setting initial state dp[ 0 ][ 0 ] = 1 # Computing DP table for digit in range ( 1 , N + 1 ): # If the current digit is 1, any # digit from [1-9] can be placed. # If N==1, 0 can also be placed if digit = = 1 : for i in range ( 0 if N = = 1 else 1 , 10 ): for mask in range ( 1 << 10 ): dp[digit][mask | ( 1 << i)] + = dp[digit - 1 ][mask] # For other positions, any digit # from [0-9] can be placed else : for i in range ( 10 ): for mask in range ( 1 << 10 ): dp[digit][mask | ( 1 << i)] + = dp[digit - 1 ][mask] # Check if all digits are # included in the mask ans = 0 for mask in range ( 1 << 10 ): if mask = = ( 1 << 10 ) - 1 : ans + = dp[N][mask] # Return the answer return ans # Driver Code if __name__ = = '__main__' : # Given Input N = 10 # Function Call print (countOfNumbers(N)) |
C#
using System; public class GFG { // Function to calculate the count of N-digit numbers // that contain all digits from [0-9] at least once public static long CountOfNumbers( int N) { // Stores the dp-states long [,] dp = new long [N + 1, 1 << 10]; // Initializing dp array with 0 for ( int i = 0; i <= N; i++) { for ( int j = 0; j < (1 << 10); j++) { dp[i, j] = 0; } } // Setting initial state dp[0, 0] = 1; // Computing DP table for ( int digit = 1; digit <= N; digit++) { // If the current digit is 1, any // digit from [1-9] can be placed. // If N==1, 0 can also be placed if (digit == 1) { for ( int i = (N == 1 ? 0 : 1); i <= 9; i++) { for ( int mask = 0; mask < (1 << 10); mask++) { dp[digit, mask | (1 << i)] += dp[digit - 1, mask]; } } } // For other positions, any digit // from [0-9] can be placed else { for ( int i = 0; i <= 9; i++) { for ( int mask = 0; mask < (1 << 10); mask++) { dp[digit, mask | (1 << i)] += dp[digit - 1, mask]; } } } } // Check if all digits are // included in the mask long ans = 0; for ( int mask = 0; mask < (1 << 10); mask++) { if (mask == (1 << 10) - 1) ans += dp[N, mask]; } // Return the answer return ans; } // Driver Code public static void Main() { // Given Input int N = 10; // Function Call Console.WriteLine(CountOfNumbers(N)); // This code is contributed by Shivam Tiwari } } |
Javascript
// Function to calculate the count of N-digit // numbers that contain all digits from [0-9] at least once function countOfNumbers(N) { // Stores the dp-states let dp = new Array(N + 1); for (let i = 0; i <= N; i++) { dp[i] = new Array(1 << 10).fill(0); } // Setting initial state dp[0][0] = 1; // Computing DP table for (let digit = 1; digit <= N; ++digit) { // If the current digit is 1, any digit from [1-9] can be placed. // If N==1, 0 can also be placed if (digit === 1) { for (let i = (N === 1 ? 0 : 1); i <= 9; ++i) { for (let mask = 0; mask < (1 << 10); ++mask) { dp[digit][mask | (1 << i)] += dp[digit - 1][mask]; } } } // For other positions, any digit from [0-9] can be placed else { for (let i = 0; i <= 9; ++i) { for (let mask = 0; mask < (1 << 10); ++mask) { dp[digit][mask | (1 << i)] += dp[digit - 1][mask]; } } } } // Check if all digits are included in the mask let ans = 0; for (let mask = 0; mask < (1 << 10); ++mask) { if (mask === (1 << 10) - 1) { ans += dp[N][mask]; } } // Return the answer return ans; } // Driver Code // Given Input let N = 10; // Function Call console.log(countOfNumbers(N)); // This Code is Contributed by Shivam Tiwari |
3265920
Time Complexity: O(N * 2^10)
Auxiliary Space: O(N * 2^10)
Contact Us