Count of numbers upto N having absolute difference of at most K between any two adjacent digits | Java program to get the count of numbers upto N having absolute difference 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
import java . util . * ; class GFG { static int [ ] [ ] [ ] [ ] dp = new int [ 1002 ] [ 10 ] [ 2 ] [ 2 ] ; static int possibleNumbers ( int pos , int previous , int tight , int start , String N , int K ) { if ( pos == N . length ( ) ) return 1 ; if ( dp [ pos ] [ previous ] [ tight ] [ start ] != - 1 ) return dp [ pos ] [ previous ] [ tight ] [ start ] ; int res = 0 ; int upper_limit = ( tight == 1 ) ? ( N . charAt ( pos ) - '0' ) : 9 ; int new_tight ; if ( start == 0 ) { res = possibleNumbers ( pos + 1 , previous , 0 , 0 , N , K ) ; for ( int 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 ( int 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 ] ; } public static void main ( String [ ] args ) { String N = "20" ; int K = 2 ; for ( int i = 0 ; i < 1002 ; i ++ ) for ( int j = 0 ; j < 10 ; j ++ ) for ( int k = 0 ; k < 2 ; k ++ ) for ( int l = 0 ; l < 2 ; l ++ ) dp [ i ] [ j ] [ k ] [ l ] = - 1 ; System . out . print ( possibleNumbers ( 0 , 0 , 1 , 0 , N , K ) + "NEW_LINE"); } }