Count numbers in a range with digit sum divisible by K having first and last digit different | Java 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 boolean 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
import java . util . * ; class GFG { static int K ; static int N ; static Vector < Integer > v = new Vector < > ( ) ; static int [ ] [ ] [ ] [ ] [ ] dp = new int [ 20 ] [ 1000 ] [ 10 ] [ 2 ] [ 2 ] ; static void init ( int x ) { for ( int i = 0 ; i < 20 ; i ++ ) for ( int j = 0 ; j < 1000 ; j ++ ) for ( int k = 0 ; k < 10 ; k ++ ) for ( int l = 0 ; l < 2 ; l ++ ) for ( int m = 0 ; m < 2 ; m ++ ) dp [ i ] [ j ] [ k ] [ l ] [ m ] = - 1 ; v . clear ( ) ; while ( x > 0 ) { v . add ( x % 10 ) ; x /= 10 ; } Collections . reverse ( v ) ; N = v . size ( ) ; } static int fun ( int pos , int sum , int st , int check , int 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 ] ; int lmt = 9 ; if ( f == 0 ) lmt = v . get ( pos ) ; int ans = 0 ; for ( int digit = 0 ; digit <= lmt ; digit ++ ) { int nf = f ; int new_sum = ( sum + digit ) % K ; int new_check = check ; int 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 ; } static void findCount ( int L , int R , int K ) { init ( R ) ; int r_ans = fun ( 0 , 0 , 0 , 0 , 0 ) ; init ( L - 1 ) ; int l_ans = fun ( 0 , 0 , 0 , 0 , 0 ) ; System . out . print ( r_ans - l_ans ) ; } public static void main ( String [ ] args ) { int L = 10 ; int R = 20 ; K = 2 ; findCount ( L , R , K ) ; } }