Count possible N | C ++ program for the above approach ; Macros for modulus ; DP array for memoization ; Utility function to count N digit numbers with digit i not appearing more than max_digit [ i ] consecutively ; If number with N digits is generated ; Create a reference variable ; Check if the current state is already computed before ; Initialize ans as zero ; Check if count of previous digit has reached zero or not ; Fill current position only with digits that are unequal to previous digit ; Else set the value of count for this new digit accordingly from max_digit [ ] ; Function to count N digit numbers with digit i not appearing more than max_digit [ i ] consecutive times ; Stores the final count ; Print the total count ; Driver Code ; Initialize the dp array with - 1 ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MOD  1000000007 NEW_LINE int dp [ 5005 ] [ 12 ] [ 12 ] ; int findCountUtil ( int N , int maxDigit [ ] , int position = 0 , int previous = 0 , int count = 1 ) { if ( position == N ) { return 1 ; } int & ans = dp [ position ] [ previous ] [ count ] ; if ( ans != -1 ) { return ans ; } ans = 0 ; for ( int i = 0 ; i <= 9 ; ++ i ) { if ( count == 0 && previous != i ) { ans = ( ans + ( findCountUtil ( N , maxDigit , position + 1 , i , maxDigit [ i ] - 1 ) ) % MOD ) % MOD ; } else if ( count != 0 ) { ans = ( ans + ( findCountUtil ( N , maxDigit , position + 1 , i , ( previous == i && position != 0 ) ? count - 1 : maxDigit [ i ] - 1 ) ) % MOD ) % MOD ; } } return ans ; } void findCount ( int N , int maxDigit [ ] ) { int ans = findCountUtil ( N , maxDigit ) ; cout << ans ; } int main ( ) { int N = 2 ; int maxDigit [ 10 ] = { 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 } ; memset ( dp , -1 , sizeof ( dp ) ) ; findCount ( N , maxDigit ) ; return 0 ; }