Count numbers in a range with digit sum divisible by K having first and last digit different | Javascript program to count numbers in a range with digit sum divisible by K having first and last digit different ; For calculating the upper bound of the sequence . ; Checking whether the sum of digits = 0 or not and the corner case as number equal to 1 ; If the state is visited then return the answer of this state directly . ; For checking whether digit to be placed is up to upper bound at the position pos or upto 9 ; Calculating new digit sum modulo k ; Check if there is a prefix of 0 s and current digit != 0 ; Then current digit will be the starting digit ; Update the bool flag that the starting digit has been found ; At n - 1 , check if current digit and starting digit are the same then no need to calculate this answer . ; Else find the answer ; Function to find the required count ; Setting up the upper bound ; Calculating F ( R ) ; Setting up the upper bound ; calculating F ( L - 1 ) ; Driver code
var K ; var N ; var v = [ ] ; var dp = Array . from ( Array ( 20 ) ) ; function init ( x ) { for ( var i = 0 ; i < 20 ; i ++ ) { dp [ i ] = Array . from ( Array ( 1000 ) , ( ) => Array ( 10 ) ) ; for ( var j = 0 ; j < 1000 ; j ++ ) { for ( var k = 0 ; k < 10 ; k ++ ) { dp [ i ] [ j ] [ k ] = Array . from ( Array ( 2 ) , ( ) => Array ( 2 ) . fill ( - 1 ) ) ; } } } v = [ ] ; while ( x > 0 ) { v . push ( x % 10 ) ; x = parseInt ( x / 10 ) ; } v . reverse ( ) ; N = v . length ; } function fun ( pos , sum , st , check , f ) { if ( pos == N ) { return ( sum == 0 && check == 1 ) ? 1 : 0 ; } if ( dp [ pos ] [ sum ] [ st ] [ check ] [ f ] != - 1 ) return dp [ pos ] [ sum ] [ st ] [ check ] [ f ] ; var lmt = 9 ; if ( f == 0 ) lmt = v [ pos ] ; var ans = 0 ; for ( var digit = 0 ; digit <= lmt ; digit ++ ) { var nf = f ; var new_sum = ( sum + digit ) % K ; var new_check = check ; var new_st = st ; if ( f == 0 && digit < lmt ) nf = 1 ; if ( check == 0 && digit != 0 ) { new_st = digit ; new_check = 1 ; } if ( pos == N - 1 && new_st == digit ) continue ; ans += fun ( pos + 1 , new_sum , new_st , new_check , nf ) ; } return dp [ pos ] [ sum ] [ st ] [ check ] [ f ] = ans ; } function findCount ( L , R , K ) { init ( R ) ; var r_ans = fun ( 0 , 0 , 0 , 0 , 0 ) ; init ( L - 1 ) ; var l_ans = fun ( 0 , 0 , 0 , 0 , 0 ) ; document . write ( r_ans - l_ans ) ; } var L = 10 ; var R = 20 ; K = 2 ; findCount ( L , R , K ) ;