357. Count Numbers with Unique Digits | Medium
Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.
Example:
Input: 2
Output: 91
Explanation: The answer should be the total numbers in the range of 0 ≤ x < 100,
excluding 11,22,33,44,55,66,77,88,99
Accepted 56,389 Submissions 121,655
For recursive solution:
Runtime: 60 ms, faster than 14.63% of Python3 online submissions for Count Numbers with Unique Digits.
For iterative solution:
Runtime: 48 ms, faster than 39.80% of Python3 online submissions for Count Numbers with Unique Digits.
class Solution:
def countNumbersWithUniqueDigits(self, n):
"""
:type n: int
:rtype: int
"""
# there must be a clever way to get a good performance
# first digit - 10 choose 1
# second digit - 9 choose 1 and so on with an exception of 0
# later revised above idea to include leading zero
# -[ ] probably can get a bit faster without recursion
# if n == 0:
# return 1
# count = 9
# for i in range(n-1):
# pick = 9 - i if 9 - i > 0 else 1
# count = count * pick
# return self.countNumbersWithUniqueDigits (n-1) + count
# iterative solution
total = 1
for i in range (n, 0, -1):
count = 9
for j in range(i-1):
pick = 9-j if 9-j > 0 else 1
count = count * pick
total += count
return total