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-stateslong long dp[100][1 << 10];// Function to calculate the count of// N-digit numbers that contains all// digits from [0-9] atleast oncelong 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 Codeint 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 approachimport 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-statesdp = [[-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 oncedef 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 InputN = 10# Function Callprint(countOfNumbers(1, 0, N)) # This code is contributed by shinjanpatra |
C#
// C# program to implement above approachusing 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-stateslet 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 oncefunction 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> |
Output
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 oncelong 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 Codeint 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 oncedef 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 Codeif __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 oncefunction 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 Inputlet N = 10;// Function Callconsole.log(countOfNumbers(N));// This Code is Contributed by Shivam Tiwari |
Output
3265920
Time Complexity: O(N * 2^10)
Auxiliary Space: O(N * 2^10)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
