Count numbers in a range with digit sum divisible by K having first and last digit different | C # 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
using System ; using System . Collections . Generic ; class GFG { static int K ; static int N ; static List < int > v = new List < int > ( ) ; 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 ; } v . Reverse ( ) ; N = v . Count ; } 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 [ 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 ) ; Console . Write ( r_ans - l_ans ) ; } public static void Main ( String [ ] args ) { int L = 10 ; int R = 20 ; K = 2 ; findCount ( L , R , K ) ; } }