Count possible N | Java 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 Fill each row with - 1. ; Function Call
import java . util . * ; class GFG { static int MOD = 1000000007 ; static int dp [ ] [ ] [ ] = new int [ 5005 ] [ 12 ] [ 12 ] ; static int findCountUtil ( int N , int maxDigit [ ] , int position , int previous , int count ) { 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 ; } static void findCount ( int N , int maxDigit [ ] ) { int position = 0 ; int previous = 0 ; int count = 1 ; int ans = findCountUtil ( N , maxDigit , position , previous , count ) ; System . out . println ( ans ) ; } public static void main ( String [ ] args ) { int N = 2 ; int [ ] maxDigit = { 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 } ; for ( int [ ] [ ] row : dp ) { for ( int [ ] rowColumn : row ) { Arrays . fill ( rowColumn , - 1 ) ; } } findCount ( N , maxDigit ) ; } }