Count the numbers with N digits and whose suffix is divisible by K | C ++ implementation to Count the numbers with N digits and whose suffix is divisible by K ; Suffix of length pos with remainder rem and Z representing whether the suffix has a non zero digit until now ; Base case ; If count of digits is less than n ; Placing all possible digits in remaining positions ; If remainder non zero and suffix has n digits ; If the subproblem is already solved ; Placing all digits at MSB of suffix and increasing it 's length by 1 ; Non zero digit is placed ; Store and return the solution to this subproblem ; Function to Count the numbers with N digits and whose suffix is divisible by K ; Since we need powers of 10 for counting , it 's better to  pre store them along with their  modulo with 1e9 + 7 for counting ; Since at each recursive step we increase the suffix length by 1 by placing digits at its leftmost position , we need powers of 10 modded with k , in order to fpos the new remainder efficiently ; Initialising dp table values - 1 represents subproblem hasn 't  been solved yet ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int mod = 1000000007 ; int dp [ 1005 ] [ 105 ] [ 2 ] ; int powers [ 1005 ] ; int powersModk [ 1005 ] ; int calculate ( int pos , int rem , int z , int k , int n ) { if ( rem == 0 && z ) { if ( pos != n ) return ( powers [ n - pos - 1 ] * 9 ) % mod ; else return 1 ; } if ( pos == n ) return 0 ; if ( dp [ pos ] [ rem ] [ z ] != -1 ) return dp [ pos ] [ rem ] [ z ] ; int count = 0 ; for ( int i = 0 ; i < 10 ; i ++ ) { if ( i == 0 ) count = ( count + ( calculate ( pos + 1 , ( rem + ( i * powersModk [ pos ] ) % k ) % k , z , k , n ) ) ) % mod ; else count = ( count + ( calculate ( pos + 1 , ( rem + ( i * powersModk [ pos ] ) % k ) % k , 1 , k , n ) ) ) % mod ; } return dp [ pos ] [ rem ] [ z ] = count ; } int countNumbers ( int n , int k ) { int st = 1 ; for ( int i = 0 ; i <= n ; i ++ ) { powers [ i ] = st ; st *= 10 ; st %= mod ; } st = 1 ; for ( int i = 0 ; i <= n ; i ++ ) { powersModk [ i ] = st ; st *= 10 ; st %= mod ; } memset ( dp , -1 , sizeof ( dp ) ) ; return calculate ( 0 , 0 , 0 , k , n ) ; } int main ( ) { int N = 2 ; int K = 2 ; cout << countNumbers ( N , K ) ; return 0 ; }