Count N digits numbers with sum divisible by K | C ++ Program to implement the above approach ; Function to count the N digit numbers whose sum is divisible by K ; Base case ; If already computed subproblem occurred ; Store the count of N digit numbers whose sum is divisible by K ; Check if the number does not contain any leading 0. ; Recurrence relation ; Driver Code ; Stores the values of overlapping subproblems
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define M  1000 NEW_LINE int countNum ( int N , int sum , int K , bool st , int dp [ M ] [ M ] [ 2 ] ) { if ( N == 0 and sum == 0 ) { return 1 ; } if ( N < 0 ) { return 0 ; } if ( dp [ N ] [ sum ] [ st ] != -1 ) { return dp [ N ] [ sum ] [ st ] ; } int res = 0 ; int start = st == 1 ? 0 : 1 ; for ( int i = start ; i <= 9 ; i ++ ) { res += countNum ( N - 1 , ( sum + i ) % K , K , ( st i > 0 ) , dp ) ; } return dp [ N ] [ sum ] [ st ] = res ; } int main ( ) { int N = 2 , K = 7 ; int dp [ M ] [ M ] [ 2 ] ; memset ( dp , -1 , sizeof ( dp ) ) ; cout << countNum ( N , 0 , K , 0 , dp ) ; }