357. Count Numbers with Unique Digits

Problem

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

Problem Summary

Given a non-negative integer n, count the number of numbers x whose digits are all different, where 0 ≤ x < 10^n.

Solution Ideas

• Output the number of n-digit numbers that do not contain repeated digits.
• After figuring out the pattern for this problem, you can directly write out all the final answers; there are only 11 answers.
• Consider how numbers with non-repeating digits are generated. If it is only a one-digit number, there are no repeated digits, and the result is 10. If it is a two-digit number, the first digit definitely cannot be 0, so the first digit has 1-9, 9 choices. To avoid repeating the first digit, the second digit can only be chosen from 0-9, 10 choices, minus the digit chosen for the first digit, so there are also 9 choices. And so on: if it is a three-digit number, the third digit has 8 choices; for a four-digit number, the fourth digit has 7 choices; for a five-digit number, the fifth digit has 6 choices; for a six-digit number, the sixth digit has 5 choices; for a seven-digit number, the seventh digit has 4 choices; for an eight-digit number, the eighth digit has 3 choices; for a nine-digit number, the ninth digit has 2 choices; for a ten-digit number, the tenth digit has 1 choice; for an eleven-digit number, the eleventh digit has 0 choices; for a twelve-digit number, the twelfth digit has 0 choices. Therefore, after the 11th digit, every number is a number with repeated digits. After knowing this pattern, you can accumulate the results above, store the results directly in an array, and use brute-force tabulation. The time complexity is O(1).

Code

package leetcode

// Brute-force tabulation method
func countNumbersWithUniqueDigits1(n int) int {
	res := []int{1, 10, 91, 739, 5275, 32491, 168571, 712891, 2345851, 5611771, 8877691}
	if n >= 10 {
		return res[10]
	}
	return res[n]
}

// Tabulation method
func countNumbersWithUniqueDigits(n int) int {
	if n == 0 {
		return 1
	}
	res, uniqueDigits, availableNumber := 10, 9, 9
	for n > 1 && availableNumber > 0 {
		uniqueDigits = uniqueDigits * availableNumber
		res += uniqueDigits
		availableNumber--
		n--
	}
	return res
}