text: Count of integers from the range [ 0 , N ] whose digit sum is a multiple of K | C # implementation of the approach ; To store the states of the dp ; Function to return the count of numbers from the range [ 0 , n ] whose digit sum is a multiple of k using bottom - up dp ; The digit in this index can only be from [ 0 , num [ idx ] ] ; The digit in this index can be anything from [ 0 , 9 ] ; new_tight is the flag value for the next position ; res can 't be negative ; Function to process the String to a vector of digits from MSD to LSD ; Driver code ; For large input number n ; Total number of digits in n ; Clean dp table ; Process the String to a vector of digits from MSD to LSD
code: using System ; using System . Collections . Generic ; class GFG { static readonly int MAX = 10005 ; static readonly int MOD = 1000000007 ; static int [ , , ] dp = new int [ MAX , 101 , 2 ] ; static int countNum ( int idx , int sum , int tight , List < int > num , int len , int k ) { if ( len == idx ) { if ( sum == 0 ) return 1 ; else return 0 ; } if ( dp [ idx , sum , tight ] != - 1 ) return dp [ idx , sum , tight ] ; int res = 0 , limit ; if ( tight == 0 ) { limit = num [ idx ] ; } else { limit = 9 ; } for ( int i = 0 ; i <= limit ; i ++ ) { int new_tight = tight ; if ( tight == 0 && i < limit ) new_tight = 1 ; res += countNum ( idx + 1 , ( sum + i ) % k , new_tight , num , len , k ) ; res %= MOD ; } if ( res < 0 ) res += MOD ; return dp [ idx , sum , tight ] = res ; } static List < int > process ( String s ) { List < int > num = new List < int > ( ) ; for ( int i = 0 ; i < s . Length ; i ++ ) { num . Add ( s [ i ] - '0' ) ; } return num ; } public static void Main ( String [ ] args ) { String n = "98765432109876543210" ; int len = n . Length ; int k = 58 ; for ( int i = 0 ; i < MAX ; i ++ ) { for ( int j = 0 ; j < 101 ; j ++ ) { for ( int l = 0 ; l < 2 ; l ++ ) dp [ i , j , l ] = - 1 ; } } List < int > num = process ( n ) ; Console . Write ( countNum ( 0 , 0 , 0 , num , len , k ) ) ; } }