Count of N | Function to return the count of such numbers ; For 1 - digit numbers , the count is 10 irrespective of K ; dp [ j ] stores the number of such i - digit numbers ending with j ; Stores the results of length i ; Initialize count for 1 - digit numbers ; Compute values for count of digits greater than 1 ; Find the range of allowed numbers if last digit is j ; Perform Range update ; Prefix sum to find actual count of i - digit numbers ending with j ; Update dp [ ] ; Stores the final answer ; Return the final answer ; Driver code
def getCount ( n , K ) : NEW_LINE INDENT if ( n == 1 ) : NEW_LINE INDENT return 10 NEW_LINE DEDENT dp = [ 0 ] * 11 NEW_LINE next = [ 0 ] * 11 NEW_LINE for i in range ( 1 , 9 + 1 ) : NEW_LINE INDENT dp [ i ] = 1 NEW_LINE DEDENT for i in range ( 2 , n + 1 ) : NEW_LINE INDENT for j in range ( 9 + 1 ) : NEW_LINE INDENT l = max ( 0 , j - k ) NEW_LINE r = min ( 9 , j + k ) NEW_LINE next [ l ] += dp [ j ] NEW_LINE next [ r + 1 ] -= dp [ j ] NEW_LINE DEDENT for j in range ( 1 , 9 + 1 ) : NEW_LINE INDENT next [ j ] += next [ j - 1 ] NEW_LINE DEDENT for j in range ( 10 ) : NEW_LINE INDENT dp [ j ] = next [ j ] NEW_LINE next [ j ] = 0 NEW_LINE DEDENT DEDENT count = 0 NEW_LINE for i in range ( 9 + 1 ) : NEW_LINE INDENT count += dp [ i ] NEW_LINE DEDENT return count NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 2 NEW_LINE k = 1 NEW_LINE print ( getCount ( n , k ) ) NEW_LINE DEDENT