Count of numbers between range having only non | C ++ implementation of the approach ; states - position , sum , rem , tight sum can have values upto 162 , if we are dealing with numbers upto 10 ^ 18 when all 18 digits are 9 , then sum is 18 * 9 = 162 ; n is the sum of digits and number should be divisible by m ; Function to return the count of required numbers from 0 to num ; Last position ; If this result is already computed simply return it ; Maximum limit upto which we can place digit . If tight is 1 , means number has already become smaller so we can place any digit , otherwise num [ pos ] ; If the current digit is zero and nonz is 1 , we can 't place it ; Function to convert x into its digit vector and uses count ( ) function to return the required count ; Initialize dp ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int M = 20 ; int dp [ M ] [ 165 ] [ M ] [ 2 ] ; int n , m ; int count ( int pos , int sum , int rem , int tight , int nonz , vector < int > num ) { if ( pos == num . size ( ) ) { if ( rem == 0 && sum == n ) return 1 ; return 0 ; } if ( dp [ pos ] [ sum ] [ rem ] [ tight ] != -1 ) return dp [ pos ] [ sum ] [ rem ] [ tight ] ; int ans = 0 ; int limit = ( tight ? 9 : num [ pos ] ) ; for ( int d = 0 ; d <= limit ; d ++ ) { if ( d == 0 && nonz ) continue ; int currSum = sum + d ; int currRem = ( rem * 10 + d ) % m ; int currF = tight || ( d < num [ pos ] ) ; ans += count ( pos + 1 , currSum , currRem , currF , nonz d , num ) ; } return dp [ pos ] [ sum ] [ rem ] [ tight ] = ans ; } int solve ( int x ) { vector < int > num ; while ( x ) { num . push_back ( x % 10 ) ; x /= 10 ; } reverse ( num . begin ( ) , num . end ( ) ) ; memset ( dp , -1 , sizeof ( dp ) ) ; return count ( 0 , 0 , 0 , 0 , 0 , num ) ; } int main ( ) { int L = 1 , R = 100 ; n = 8 , m = 2 ; cout << solve ( R ) - solve ( L ) ; return 0 ; }