Count N digits numbers with sum divisible by K | Java 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
import java . util . * ; import java . lang . * ; class GFG { static final 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 ; } public static void main ( String [ ] args ) { int N = 2 , K = 7 ; int [ ] [ ] [ ] dp = new int [ M ] [ M ] [ 2 ] ; for ( int [ ] [ ] i : dp ) for ( int [ ] j : i ) Arrays . fill ( j , - 1 ) ; System . out . print ( countNum ( N , 0 , K , 0 , dp ) ) ; } }