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 whoe 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
using System ; class GFG { static int M = 1000 ; static int countNum ( int N , int sum , int K , int st , int [ , , ] dp ) { if ( N == 0 && 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 ) ? 1 : 0 , dp ) ; } return dp [ N , sum , st ] = res ; } static public void Main ( ) { int N = 2 , K = 7 ; int [ , , ] dp = new int [ M , M , 2 ] ; for ( int i = 0 ; i < M ; i ++ ) for ( int j = 0 ; j < M ; j ++ ) for ( int k = 0 ; k < 2 ; k ++ ) dp [ i , j , k ] = - 1 ; Console . WriteLine ( countNum ( N , 0 , K , 0 , dp ) ) ; } }