Count possible N-digit numbers such that each digit does not appear more than given number of times consecutively
Given an integer N and an array maxDigit[], the task is to count all the distinct N-digit numbers such that digit i does not appear more than maxDigit[i] times. Since the count can be very large, print it modulo 109 + 7.
Examples:
Input: N = 2, maxDigit[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Output: 90
Explanation:
Any digit can’t appear more than once consecutively. Therefore, numbers [00, 11, 22, 33, 44, 55, 66, 77, 88, 99] are invalid.
Hence, the total numbers without any restrictions are 10×10 = 100.
Therefore, the count is 100 – 10 = 90.Input: N = 3, maxDigit[] = {2, 1, 1, 1, 1, 2, 1, 1, 1, 2}
Output: 864
Naive Approach: The simplest approach is to iterate over all the N-digit numbers and count those numbers that satisfy the given conditions. After checking all the numbers, print the total count modulo 109 + 7.
Time Complexity: O(N*10N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use the concept of Digit Dynamic Programming. The DP states for this problem are explained as follows:
- In Digit-DP, the idea is to build a number from left to right by placing a digit [0, 9] at every position. So, to keep track of the current position, it is required to have a position state. This state will have possible values from 0 to (N – 1).
- According to the question, a digit i can’t appear more than maxDigit[i] consecutive times, therefore keep track of the previously filled digit. So, a state previous is required. This state will have possible values from 0 to 9.
- A state count is required which will provide the number of times a digit can appear consecutively. This state will have possible values from 1 to maxDigit[i].
Follow the steps below to solve this problem:
- The first position can have any digit without any restrictions.
- From the second position and onwards, keep a track of the previously filled digit and its given count up to which it can appear consecutively.
- If the same digit appears on the next position, then decrement its count and if this count becomes zero, simply ignore this digit in the next recursive call.
- If a different digit appears on the next position, then update its count according to the given value in maxDigit[].
- At each of the above recursive calls when the resultant number is generated then increment the count for that number.
- After the above steps, print the value of the total count as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Macros for modulus #define MOD 1000000007 // DP array for memoization int dp[5005][12][12]; // Utility function to count N digit // numbers with digit i not appearing // more than max_digit[i] consecutively int findCountUtil( int N, int maxDigit[], int position = 0, int previous = 0, int count = 1) { // If number with N digits // is generated if (position == N) { return 1; } // Create a reference variable int & ans = dp[position][previous][count]; // Check if the current state is // already computed before if (ans != -1) { return ans; } // Initialize ans as zero ans = 0; for ( int i = 0; i <= 9; ++i) { // Check if count of previous // digit has reached zero or not if (count == 0 && previous != i) { // Fill current position // only with digits that // are unequal to previous digit ans = (ans + (findCountUtil(N, maxDigit, position + 1, i, maxDigit[i] - 1)) % MOD) % MOD; } else if (count != 0) { // If by placing the same digit // as previous on the current // position, decrement count by 1 // Else set the value of count // for this new digit // accordingly from max_digit[] ans = (ans + (findCountUtil( N, maxDigit, position + 1, i, (previous == i && position != 0) ? count - 1 : maxDigit[i] - 1)) % MOD) % MOD; } } return ans; } // Function to count N digit numbers // with digit i not appearing more // than max_digit[i] consecutive times void findCount( int N, int maxDigit[]) { // Stores the final count int ans = findCountUtil(N, maxDigit); // Print the total count cout << ans; } // Driver Code int main() { int N = 2; int maxDigit[10] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; // Initialize the dp array with -1 memset (dp, -1, sizeof (dp)); // Function Call findCount(N, maxDigit); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Macros for modulus static int MOD = 1000000007 ; // DP array for memoization static int dp[][][] = new int [ 5005 ][ 12 ][ 12 ]; // Utility function to count N digit // numbers with digit i not appearing // more than max_digit[i] consecutively static int findCountUtil( int N, int maxDigit[], int position, int previous, int count) { // If number with N digits // is generated if (position == N) { return 1 ; } // Create a reference variable int ans = dp[position][previous][count]; // Check if the current state is // already computed before if (ans != - 1 ) { return ans; } // Initialize ans as zero ans = 0 ; for ( int i = 0 ; i <= 9 ; ++i) { // Check if count of previous // digit has reached zero or not if (count == 0 && previous != i) { // Fill current position // only with digits that // are unequal to previous digit ans = (ans + (findCountUtil( N, maxDigit, position + 1 , i, maxDigit[i] - 1 )) % MOD) % MOD; } else if (count != 0 ) { // If by placing the same digit // as previous on the current // position, decrement count by 1 // Else set the value of count // for this new digit // accordingly from max_digit[] ans = (ans + (findCountUtil( N, maxDigit, position + 1 , i, (previous == i && position != 0 ) ? count - 1 : maxDigit[i] - 1 )) % MOD) % MOD; } } return ans; } // Function to count N digit numbers // with digit i not appearing more // than max_digit[i] consecutive times static void findCount( int N, int maxDigit[]) { int position = 0 ; int previous = 0 ; int count = 1 ; // Stores the final count int ans = findCountUtil(N, maxDigit, position, previous, count); // Print the total count System.out.println(ans); } // Driver Code public static void main (String[] args) { int N = 2 ; int [] maxDigit = { 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 }; // Initialize the dp array with -1 // Fill each row with -1. for ( int [][] row : dp) { for ( int [] rowColumn : row) { Arrays.fill(rowColumn, - 1 ); } } // Function Call findCount(N, maxDigit); } } // This code is contributed by susmitakundugoaldanga |
Python3
# Python3 program for the above approach # Macros for modulus # DP array for memoization dp = [[[ - 1 for i in range ( 5005 )] for i in range ( 12 ) ] for i in range ( 12 )] # Utility function to count N digit # numbers with digit i not appearing # more than max_digit[i] consecutively def findCountUtil(N, maxDigit, position ,previous ,count): global dp # If number with N digits # is generated if (position = = N): return 1 # Create a reference variable ans = dp[position][previous][count] # Check if the current state is # already computed before if (ans ! = - 1 ): return ans # Initialize ans as zero ans = 0 for i in range ( 10 ): # Check if count of previous # digit has reached zero or not if (count = = 0 and previous ! = i): # Fill current position # only with digits that # are unequal to previous digit ans = (ans + (findCountUtil(N, maxDigit, position + 1 , i, maxDigit[i] - 1 )) % 1000000007 ) % 1000000007 elif (count ! = 0 ): # If by placing the same digit # as previous on the current # position, decrement count by 1 # Else set the value of count # for this new digit # accordingly from max_digit[] ans = (ans + (findCountUtil(N, maxDigit, position + 1 , i, count - 1 if (previous = = i and position ! = 0 ) else maxDigit[i] - 1 )) % 1000000007 ) % 1000000007 dp[position][previous][count] = ans return ans # Function to count N digit numbers # with digit i not appearing more # than max_digit[i] consecutive times def findCount(N, maxDigit): # Stores the final count ans = findCountUtil(N, maxDigit, 0 , 0 , 1 ) # Print the total count print (ans) # Driver Code if __name__ = = '__main__' : N = 2 maxDigit = [ 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ] # Function Call findCount(N, maxDigit) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; using System.Collections.Generic; using System; using System.Collections.Generic; public class GFG{ // Macros for modulus static int MOD = 1000000007; // DP array for memoization static int [,,]dp = new int [5005, 12, 12]; // Utility function to count N digit // numbers with digit i not appearing // more than max_digit[i] consecutively static int findCountUtil( int N, int []maxDigit, int position, int previous, int count) { // If number with N digits // is generated if (position == N) { return 1; } // Create a reference variable int ans = dp[position, previous, count]; // Check if the current state is // already computed before if (ans != -1) { return ans; } // Initialize ans as zero ans = 0; for ( int i = 0; i <= 9; ++i) { // Check if count of previous // digit has reached zero or not if (count == 0 && previous != i) { // Fill current position // only with digits that // are unequal to previous digit ans = (ans + (findCountUtil( N, maxDigit, position + 1, i, maxDigit[i] - 1)) % MOD) % MOD; } else if (count != 0) { // If by placing the same digit // as previous on the current // position, decrement count by 1 // Else set the value of count // for this new digit // accordingly from max_digit[] ans = (ans + (findCountUtil( N, maxDigit, position + 1, i, (previous == i && position != 0) ? count - 1 : maxDigit[i] - 1)) % MOD) % MOD; } } return ans; } // Function to count N digit numbers // with digit i not appearing more // than max_digit[i] consecutive times static void findCount( int N, int []maxDigit) { int position = 0; int previous = 0; int count = 1; // Stores the readonly count int ans = findCountUtil(N, maxDigit, position, previous, count); // Print the total count Console.WriteLine(ans); } // Driver Code public static void Main(String[] args) { int N = 2; int [] maxDigit = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; // Initialize the dp array with -1 // Fill each row with -1. for ( int i = 0; i < dp.GetLength(0); i++) { for ( int j = 0; j < dp.GetLength(1); j++) { for ( int k = 0; k < dp.GetLength(2); k++) dp[i, j, k] = -1; } } // Function Call findCount(N, maxDigit); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for the above approach // Macros for modulus let MOD = 1000000007; // DP array for memoization let dp = new Array(5005); for (let i = 0; i < 12; i++) { dp[i] = new Array(12); for (let j = 0; j < 12; j++) { dp[i][j] = new Array(12); for (let k = 0; k < 12; k++) { dp[i][j][k] = -1; } } } // Utility function to count N digit // numbers with digit i not appearing // more than max_digit[i] consecutively function findCountUtil(N, maxDigit, position, previous, count) { // If number with N digits // is generated if (position == N) { return 1; } // Create a reference variable let ans = dp[position][previous][count]; // Check if the current state is // already computed before if (ans != -1) { return ans; } // Initialize ans as zero ans = 0; for (let i = 0; i <= 9; ++i) { // Check if count of previous // digit has reached zero or not if (count == 0 && previous != i) { // Fill current position // only with digits that // are unequal to previous digit ans = (ans + (findCountUtil( N, maxDigit, position + 1, i, maxDigit[i] - 1)) % MOD) % MOD; } else if (count != 0) { // If by placing the same digit // as previous on the current // position, decrement count by 1 // Else set the value of count // for this new digit // accordingly from max_digit[] ans = (ans + (findCountUtil( N, maxDigit, position + 1, i, (previous == i && position != 0) ? count - 1 : maxDigit[i] - 1)) % MOD) % MOD; } } return ans; } // Function to count N digit numbers // with digit i not appearing more // than max_digit[i] consecutive times function findCount(N, maxDigit) { let position = 0; let previous = 0; let count = 1; // Stores the final count let ans = findCountUtil(N, maxDigit, position, previous, count); // Print the total count document.write(ans); } let N = 2; let maxDigit = [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]; // Function Call findCount(N, maxDigit); // This code is contributed by decode2207. </script> |
90
Time Complexity: O(N*10*10)
Auxiliary Space: O(N*10*10)
Efficient approach : DP tabulation ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memorization(top-down) because memorization method needs extra stack space of recursion calls.
Implementations Steps :
- Initialize a three-dimensional DP array dp[N][10][10] to store the number of N digit numbers with the ith digit not appearing more than maxDigit[i] times consecutively.
- Initialize the base cases of the DP array as dp[0][i][1] = 1 for all i from 0 to 9.
- Iterate through each digit i from 0 to 9, and for each digit i, iterate through each digit k from 0 to 9, and for each digit k, iterate through each length l from 1 to maxDigit[i].
- If i is not equal to k, then the number of N digit numbers with the ith digit not appearing more than maxDigit[i] times consecutively is incremented by dp[i][j][1] += dp[i – 1][k][l].
- If i is equal to k, then the number of N digit numbers with the ith digit not appearing more than maxDigit[i] times consecutively is incremented by dp[i][j][l + 1] += dp[i – 1][k][l].
- Iterate through each digit i from 0 to 9, and for each digit i, iterate through each length l from 1 to maxDigit[i], and increment the final answer by dp[N – 1][i][l].
- Print the final answer.
Implementation :
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Macros for modulus #define MOD 1000000007 // Utility function to count N digit // numbers with digit i not appearing // more than max_digit[i] consecutively void findCount( int N, int maxDigit[]) { // DP array for memoization int dp[5005][12][12]; // Initialize the dp array with 0 memset (dp, 0, sizeof (dp)); // Fill the base cases for ( int i = 0; i <= 9; ++i) { dp[0][i][1] = 1; } // Fill the dp table for ( int i = 1; i < N; ++i) { for ( int j = 0; j <= 9; ++j) { for ( int k = 0; k <= 9; ++k) { for ( int l = 1; l <= maxDigit[j]; ++l) { if (k != j) { dp[i][j][1] = (dp[i][j][1] + dp[i - 1][k][l]) % MOD; } else { dp[i][j][l + 1] = (dp[i][j][l + 1] + dp[i - 1][k][l]) % MOD; } } } } } // Find the final count int ans = 0; for ( int i = 0; i <= 9; ++i) { for ( int j = 1; j <= maxDigit[i]; ++j) { ans = (ans + dp[N - 1][i][j]) % MOD; } } // Print the total count cout << ans; } // Driver Code int main() { int N = 2; int maxDigit[10] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; // Function Call findCount(N, maxDigit); return 0; } // this code is contributed by bhardwajji |
Java
import java.util.*; public class Main { // Utility function to count N digit // numbers with digit i not appearing // more than max_digit[i] consecutively static void findCount( int N, int [] maxDigit) { // DP array for memoization int [][][] dp = new int [ 5005 ][ 12 ][ 12 ]; // Initialize the dp array with 0 for ( int [][] a : dp) { for ( int [] b : a) { Arrays.fill(b, 0 ); } } // Fill the base cases for ( int i = 0 ; i <= 9 ; ++i) { dp[ 0 ][i][ 1 ] = 1 ; } // Fill the dp table for ( int i = 1 ; i < N; ++i) { for ( int j = 0 ; j <= 9 ; ++j) { for ( int k = 0 ; k <= 9 ; ++k) { for ( int l = 1 ; l <= maxDigit[j]; ++l) { if (k != j) { dp[i][j][ 1 ] = (dp[i][j][ 1 ] + dp[i - 1 ][k][l]) % 1000000007 ; } else { dp[i][j][l + 1 ] = (dp[i][j][l + 1 ] + dp[i - 1 ][k][l]) % 1000000007 ; } } } } } // Find the final count int ans = 0 ; for ( int i = 0 ; i <= 9 ; ++i) { for ( int j = 1 ; j <= maxDigit[i]; ++j) { ans = (ans + dp[N - 1 ][i][j]) % 1000000007 ; } } // Print the total count System.out.println(ans); } // Driver code public static void main(String[] args) { int N = 2 ; int [] maxDigit = { 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 }; // Function call findCount(N, maxDigit); } } |
Python3
MOD = 1000000007 def findCount(N, maxDigit): # DP array for memoization dp = [[[ 0 for _ in range ( 12 )] for _ in range ( 10 )] for _ in range (N + 1 )] # Fill the base cases for i in range ( 10 ): dp[ 0 ][i][ 1 ] = 1 # Fill the dp table for i in range ( 1 , N): for j in range ( 10 ): for k in range ( 10 ): for l in range ( 1 , maxDigit[j] + 1 ): if k ! = j: dp[i][j][ 1 ] = (dp[i][j][ 1 ] + dp[i - 1 ][k][l]) % MOD else : dp[i][j][l + 1 ] = (dp[i][j][l + 1 ] + dp[i - 1 ][k][l]) % MOD # Find the final count ans = 0 for i in range ( 10 ): for j in range ( 1 , maxDigit[i] + 1 ): ans = (ans + dp[N - 1 ][i][j]) % MOD # Print the total count print (ans) # Driver code N = 2 maxDigit = [ 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ] findCount(N, maxDigit) |
C#
using System; class Program { const int MOD = 1000000007; static void findCount( int N, int [] maxDigit) { // DP array for memoization int [,,] dp = new int [5005, 12, 12]; // Initialize the dp array with 0 Array.Clear(dp, 0, dp.Length); // Fill the base cases for ( int i = 0; i <= 9; ++i) { dp[0, i, 1] = 1; } // Fill the dp table for ( int i = 1; i < N; ++i) { for ( int j = 0; j <= 9; ++j) { for ( int k = 0; k <= 9; ++k) { for ( int l = 1; l <= maxDigit[j]; ++l) { if (k != j) { dp[i, j, 1] = (dp[i, j, 1] + dp[i - 1, k, l]) % MOD; } else { dp[i, j, l + 1] = (dp[i, j, l + 1] + dp[i - 1, k, l]) % MOD; } } } } } // Find the final count int ans = 0; for ( int i = 0; i <= 9; ++i) { for ( int j = 1; j <= maxDigit[i]; ++j) { ans = (ans + dp[N - 1, i, j]) % MOD; } } // Print the total count Console.WriteLine(ans); } static void Main( string [] args) { int N = 2; int [] maxDigit = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; // Function Call findCount(N, maxDigit); } } |
Javascript
// Utility function to count N digit // numbers with digit i not appearing // more than max_digit[i] consecutively function findCount(N, maxDigit) { // DP array for memoization let dp = new Array(5005).fill( null ).map(() => new Array(12).fill( null ).map(() => new Array(12).fill(0))); // Fill the base cases for (let i = 0; i <= 9; ++i) { dp[0][i][1] = 1; } // Fill the dp table for (let i = 1; i < N; ++i) { for (let j = 0; j <= 9; ++j) { for (let k = 0; k <= 9; ++k) { for (let l = 1; l <= maxDigit[j]; ++l) { if (k != j) { dp[i][j][1] = (dp[i][j][1] + dp[i - 1][k][l]) % 1000000007; } else { dp[i][j][l + 1] = (dp[i][j][l + 1] + dp[i - 1][k][l]) % 1000000007; } } } } } // Find the final count let ans = 0; for (let i = 0; i <= 9; ++i) { for (let j = 1; j <= maxDigit[i]; ++j) { ans = (ans + dp[N - 1][i][j]) % 1000000007; } } // Print the total count console.log(ans); } // Driver Code let N = 2; let maxDigit = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]; // Function Call findCount(N, maxDigit); |
90
Time Complexity: O(N * 10 * 10 * maxDigit)
Auxiliary Space: O(N*10*10)