This is a classic combinatorics problem. In order to count all distinct numbers, we go digit by digit.
We can choose digits using the following rules:
1st digit: 1-9
2nd - nth digit: 0-9
In order to ensure distinctness of digits, we need to add more rules on 2nd to nth digits.
2nd digit can now only select from 0-9 except the first digit, 9 - 1 = 8 choices
3rd digit can now select from 0-9 except the first two digits, 9 - 2 = 7 choices
nth digit follows the same rules. 9 - (n-1) choices, if n == 10, then we have 0 choices left.
Putting the above rules into some compact code, we get the following:
def countNumbersWithUniqueDigits(self, n): from operator import mul; from functools import reduce s = 1 for i in range(1,n+1): s += 9 * reduce(mul, [j for j in range(9, 9-i+1,-1)], 1) return s