Count of numbers in range which are divisible by M and have digit D at odd places | C # 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
using System ; using System . Collections . Generic ; class Graph { static int m , n , d ; static List < int > v = new List < int > ( ) ; static int k = ( int ) 1e9 + 7 ; static int [ , , ] dp = new int [ 2001 , 2001 , 2 ] ; static void init ( string 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 [ i ] - '0' ) ; } n = l . Length ; } static string number_minus_one ( string a ) { string s = a . Substring ( 1 ) ; string s1 = " " ; for ( int i = 0 ; i < s . Length - 1 ; i ++ ) s1 += '0' ; if ( a [ 0 ] == '1' && String . Compare ( s , s1 ) == 0 ) { int l = s . Length ; a = a . Replace ( a [ 0 ] , '0' ) ; for ( int i = 0 ; i < l ; i ++ ) a += '9' ; } else { for ( int i = a . Length - 1 ; i >= 0 ; i -- ) { if ( a [ i ] == '0' ) a = a . Replace ( a [ i ] , '9' ) ; else { a = a . Replace ( a [ i ] , ( char ) ( ( ( a [ 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 [ 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 ; } } dp [ pos , sum , f ] = ans ; return dp [ pos , sum , f ] ; } static void operations ( string L , string R ) { init ( R ) ; int ans = fun ( 0 , 0 , 0 ) ; L = number_minus_one ( L ) ; init ( L ) ; ans -= fun ( 0 , 0 , 0 ) ; if ( ans < 0 ) ans += k ; Console . WriteLine ( ans ) ; } public static void Main ( String [ ] args ) { m = 2 ; d = 2 ; int Q = 1 ; string [ , ] arr = { { "20" , "32" } } ; for ( int i = 0 ; i < Q ; i ++ ) { operations ( arr [ i , 0 ] , arr [ i , 1 ] ) ; } } }