Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.


    Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])


Credits:Special thanks to @memoryless for adding this problem and creating all test cases.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Mathematics

Complete search

Starter code: class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        

Solutions:
class Solution:

	def countNumbersWithUniqueDigits(self, n):
		ls = [1, 10, 91]
		mul = 9
		res = 0
		for i in range(8):
			mul = 9
			m = 9
			for j in range(i + 2):
				mul *= m
				m -= 1
			ls.append(mul + ls[-1])
		if n >= 9:
			return ls[9]
		else:
			return ls[n]


class Solution:

	def countNumbersWithUniqueDigits(self, n):
		answer = 10 ** n
		for i in range(1, n + 1):
			all_count = 9 * 10 ** (i - 1)
			invalid = 9
			for j in range(1, i):
				invalid *= 10 - j
			answer -= all_count - invalid
		return answer


class Solution:

	def countNumbersWithUniqueDigits(self, n):
		choices = [9, 9, 8, 7, 6, 5, 4, 3, 2, 1]
		(ans, product) = (1, 1)
		for i in range(n if n <= 10 else 10):
			product *= choices[i]
			ans += product
		return ans


class Solution:

	def countNumbersWithUniqueDigits(self, n):
		if n == 0:
			return 1
		if n > 10:
			return self.countNumbersWithUniqueDigits(10)
		count = 0
		for i in range(1, n + 1):
			temp = 1
			for j in range(i):
				temp *= 10 - j
			if temp > 10:
				temp = temp // 10 * 9
			count += temp
		return count


class Solution:

	def countNumbersWithUniqueDigits(self, n):
		digits = [1, 10, 91, 739, 5275, 32491, 168571, 712891, 2345851, 5611771, 8877691]
		if n < len(digits):
			return digits[n]
		return digits[-1]


class Solution:

	def countNumbersWithUniqueDigits(self, n):
		if n == 0:
			return 1
		ans = 10
		d = 9
		prod = 9
		for i in range(2, n + 1):
			prod *= d
			d -= 1
			ans += prod
		return ans


class Solution:

	def countNumbersWithUniqueDigits(self, n):
		if n == 0:
			return 1
		digits = [9, 9, 8, 7, 6, 5, 4, 3, 2, 1]
		ans = 0
		while n > 0:
			if n == 1:
				ans += 10
			else:
				res = 1
				for i in range(n):
					res *= digits[i]
				ans += res
			n -= 1
		return ans


class Solution:

	def countNumbersWithUniqueDigits(self, n):
		if n == 0:
			return 1
		elif n == 1:
			return 10
		else:
			return (self.countNumbersWithUniqueDigits(n - 1) - self.countNumbersWithUniqueDigits(n - 2)) * (11 - n) + self.countNumbersWithUniqueDigits(n - 1)