computing count of numbers from 1 to 10 ^ d - 1 , d = 0 a [ 0 ] = 0 d = 1 a [ 1 ] = count of numbers from 0 to 9 = 1 d = 2 a [ 2 ] = count of numbers from 0 to 99 = a [ 1 ] * 9 + 10 = 19 d = 3 a [ 3 ] = count of numbers from 0 to 999 = a [ 2 ] * 19 + 100 = 171
a = [ 1 for i in range ( d + 1 ) ] NEW_LINE a [ 0 ] = 0 NEW_LINE if len ( a ) > 1 : NEW_LINE INDENT a [ 1 ] = 1 NEW_LINE DEDENT for i in range ( 2 , d + 1 ) : NEW_LINE INDENT a [ i ] = a [ i - 1 ] * 9 + mt . ceil ( pow ( 10 , i - 1 ) ) NEW_LINE DEDENT