Count of numbers upto N having absolute difference of at most K between any two adjacent digits | Table to store solution of each subproblem ; Function to calculate all possible numbers ; Check if position reaches end that is equal to length of N ; Check if the result is already computed simply return it ; Maximum limit upto which we can place digit . If tight is false , means number has already become smaller so we can place any digit , otherwise N [ pos ] ; Check if start is false the number has not started yet ; Check if we do not start the number at pos then recur forward ; If we start the number we can place any digit from 1 to upper_limit ; Finding the new tight ; Condition if the number has already started ; We can place digit upto upperbound & absolute difference with previous digit much be atmost K ; Absolute difference atmost K ; Store the solution to this subproblem ; Driver code ; Initialising the table with - 1 ; Function call
let dp = new Array ( 1002 ) ; function possibleNumbers ( pos , previous , tight , start , N , K ) { if ( pos == N . length ) return 1 ; if ( dp [ pos ] [ previous ] [ tight ] [ start ] != - 1 ) return dp [ pos ] [ previous ] [ tight ] [ start ] ; let res = 0 ; let upper_limit = ( tight == 1 ) ? ( N [ pos ] - ' ' ) : 9 ; let new_tight ; if ( start == 0 ) { res = possibleNumbers ( pos + 1 , previous , 0 , 0 , N , K ) ; for ( let i = 1 ; i <= upper_limit ; i ++ ) { new_tight = ( tight > 0 && i == upper_limit ) ? 1 : 0 ; res += possibleNumbers ( pos + 1 , i , new_tight , 1 , N , K ) ; } } else { for ( let i = 0 ; i <= upper_limit ; i ++ ) { new_tight = ( tight > 0 && i == upper_limit ) ? 1 : 0 ; if ( Math . abs ( i - previous ) <= K ) res += possibleNumbers ( pos + 1 , i , new_tight , 1 , N , K ) ; } } dp [ pos ] [ previous ] [ tight ] [ start ] = res ; return dp [ pos ] [ previous ] [ tight ] [ start ] ; } let N = " " ; let K = 2 ; for ( let i = 0 ; i < 1002 ; i ++ ) { dp [ i ] = new Array ( 10 ) ; for ( let j = 0 ; j < 10 ; j ++ ) { dp [ i ] [ j ] = new Array ( 2 ) ; for ( let k = 0 ; k < 2 ; k ++ ) { dp [ i ] [ j ] [ k ] = new Array ( 2 ) ; for ( let l = 0 ; l < 2 ; l ++ ) { dp [ i ] [ j ] [ k ] [ l ] = - 1 ; } } } } document . write ( possibleNumbers ( 0 , 0 , 1 , 0 , N , K ) + " " ) ;