Count of numbers upto N digits formed using digits 0 to K | Javascript implementation to count the numbers upto N digits such that no two zeros are adjacent ; Function to count the numbers upto N digits such that no two zeros are adjacent ; Condition to check if only one element remains ; If last element is non zero , return K - 1 ; If last element is 0 ; Condition to check if value calculated already ; If last element is non zero , then two cases arise , current element can be either zero or non zero ; Memoize this case ; If last is 0 , then current can only be non zero ; Memoize and return ; Given N and K ; Function Call
var dp = Array . from ( Array ( 15 ) , ( ) => Array ( 10 ) . fill ( 0 ) ) ; function solve ( n , last , k ) { if ( n == 1 ) { if ( last == k ) { return ( k - 1 ) ; } else { return 1 ; } } if ( ( dp [ n ] [ last ] ) != 0 ) return dp [ n ] [ last ] ; if ( last == k ) { return dp [ n ] [ last ] = ( k - 1 ) * solve ( n - 1 , k , k ) + ( k - 1 ) * solve ( n - 1 , 1 , k ) ; } else { dp [ n ] [ last ] = solve ( n - 1 , k , k ) ; return dp [ n ] [ last ] ; } } var n = 2 , k = 3 ; var x = solve ( n , k , k ) + solve ( n , 1 , k ) ; document . write ( x ) ;