Count of numbers in range which are divisible by M and have digit D at odd places | Java program to find the count of numbers in the range [ L , R ] which are divisible by M and have digit D at the odd places ; Variables to store M , N , D ; Vector to store the digit number in the form of digits ; Dp table to compute the answer ; Function to add the individual digits into the vector ; Iterating through the number and adding the digits into the vector ; Function to subtract 1 from a number represented in a form of a String ; Iterating through the number ; If the first digit is 1 , then make it 0 and add 9 at the end of the String . ; If we need to subtract 1 from 0 , then make it 9 and subtract 1 from the previous digits ; Else , simply subtract 1 ; Function to find the count of numbers in the range [ L , R ] which are divisible by M and have digit D at the odd places ; Base case ; If we have built N - digit number and the number is divisible by m then we have got one possible answer . ; If the answer has already been computed , then return the answer ; The possible digits which we can place at the pos position . ; Iterating through all the digits ; If we have placed all the digits up to pos - 1 equal to their limit and currently we are placing a digit which is smaller than this position 's limit then we can place  0 to 9 at all the next positions  to make the number smaller than R ; Calculating the number upto pos mod m . ; Combinations of numbers as there are 10 digits in the range [ 0 , 9 ] ; Recursively call the function for the next position ; Returning the final answer ; Function to call the function for every query ; Driver code
import java . util . ArrayList ; import java . util . Arrays ; class Graph { static int m , n , d ; static ArrayList < Integer > v = new ArrayList < > ( ) ; static final int k = ( int ) 1e9 + 7 ; static int [ ] [ ] [ ] dp = new int [ 2001 ] [ 2001 ] [ 2 ] ; static void init ( StringBuilder l ) { for ( int i = 0 ; i < 2001 ; i ++ ) { for ( int j = 0 ; j < 2001 ; j ++ ) { for ( int k = 0 ; k < 2 ; k ++ ) { dp [ i ] [ j ] [ k ] = - 1 ; } } } v . clear ( ) ; for ( int i = 0 ; i < l . length ( ) ; i ++ ) { v . add ( l . charAt ( i ) - '0' ) ; } n = l . length ( ) ; } static String number_minus_one ( StringBuilder a ) { String s = a . substring ( 1 ) ; String s1 = " " ; for ( int i = 0 ; i < s . length ( ) - 1 ; i ++ ) s1 += '0' ; if ( a . charAt ( 0 ) == '1' && s . compareTo ( s1 ) == 0 ) { int l = s . length ( ) ; a = new StringBuilder ( " " ) ; a . append ( '0' ) ; for ( int i = 0 ; i < l ; i ++ ) a . append ( '9' ) ; } else { for ( int i = a . length ( ) - 1 ; i >= 0 ; i -- ) { if ( a . charAt ( i ) == '0' ) a . setCharAt ( i , '9' ) ; else { a . setCharAt ( i , ( char ) ( ( ( a . charAt ( i ) - '0' ) - 1 ) + '0' ) ) ; break ; } } } return a . toString ( ) ; } static int fun ( int pos , int sum , int f ) { if ( pos == n ) { if ( sum == 0 ) { return 1 ; } return 0 ; } if ( dp [ pos ] [ sum ] [ f ] != - 1 ) return dp [ pos ] [ sum ] [ f ] ; int lmt = 9 ; if ( f == 0 ) lmt = v . get ( pos ) ; int ans = 0 ; for ( int i = 0 ; i <= lmt ; i ++ ) { if ( i == d && pos % 2 == 1 ) ans += 0 ; else if ( i != d && pos % 2 == 0 ) ans += 0 ; else { int new_f = f ; if ( f == 0 && i < lmt ) new_f = 1 ; int new_sum = sum ; new_sum *= 10 ; new_sum += i ; new_sum %= m ; ans += fun ( pos + 1 , new_sum , new_f ) ; ans %= k ; } } return dp [ pos ] [ sum ] [ f ] = ans ; } static void operations ( StringBuilder L , StringBuilder R ) { init ( R ) ; int ans = fun ( 0 , 0 , 0 ) ; L = new StringBuilder ( number_minus_one ( L ) ) ; init ( L ) ; ans -= fun ( 0 , 0 , 0 ) ; if ( ans < 0 ) ans += k ; System . out . println ( ans ) ; } public static void main ( String [ ] args ) { m = 2 ; d = 2 ; int Q = 1 ; StringBuilder [ ] [ ] arr = { { new StringBuilder ( "20" ) , new StringBuilder ( "32" ) } } ; for ( int i = 0 ; i < Q ; i ++ ) { operations ( arr [ i ] [ 0 ] , arr [ i ] [ 1 ] ) ; } } }