Count N digits numbers with sum divisible by K | 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
def countNum ( N , sum , K , st , dp ) : NEW_LINE INDENT if ( N == 0 and sum == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( N < 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ N ] [ sum ] [ st ] != - 1 ) : NEW_LINE INDENT return dp [ N ] [ sum ] [ st ] NEW_LINE DEDENT res = 0 NEW_LINE start = 1 NEW_LINE if ( st == 1 ) : NEW_LINE INDENT start = 0 NEW_LINE DEDENT else : NEW_LINE INDENT start = 1 NEW_LINE DEDENT for i in range ( start , 10 ) : NEW_LINE INDENT min = 0 NEW_LINE if ( ( st i ) > 0 ) : NEW_LINE INDENT min = 1 NEW_LINE DEDENT else : NEW_LINE INDENT min = 0 NEW_LINE DEDENT res += countNum ( N - 1 , ( sum + i ) % K , K , min , dp ) NEW_LINE dp [ N ] [ sum ] [ st ] = res NEW_LINE DEDENT return dp [ N ] [ sum ] [ st ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 2 NEW_LINE K = 7 NEW_LINE M = 100 NEW_LINE dp = [ [ [ - 1 for i in range ( 2 ) ] for j in range ( M ) ] for j in range ( M ) ] NEW_LINE print ( countNum ( N , 0 , K , 0 , dp ) ) NEW_LINE DEDENT