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: #include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  100005 NEW_LINE #define MOD  1000000007 NEW_LINE int dp [ MAX ] [ 101 ] [ 2 ] ; int countNum ( int idx , int sum , int tight , vector < 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 ; } vector < int > process ( string s ) { vector < int > num ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { num . push_back ( s [ i ] - '0' ) ; } return num ; } int main ( ) { string n = "98765432109876543210" ; int len = n . length ( ) ; int k = 58 ; memset ( dp , -1 , sizeof ( dp ) ) ; vector < int > num = process ( n ) ; cout << countNum ( 0 , 0 , 0 , num , len , k ) ; return 0 ; }