Question
Formatted question description: https://leetcode.ca/all/357.html
357 Count Numbers with Unique Digits
Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10^n.
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
@tag-dp
@tag-math
Algorithm
Three digits
11 can be 110 or 101
22 can be 220 or 202
So there are only 8 possibilities
10 +
90-9 +
(90-9) * 8
In four digits
111 can be 1010, 1101, 1110
There are only 7 possibilities
- One-digit number that meets the requirements is 10 (0 to 9)
- The two-digit number that satisfies the meaning of the question is 81, [10-99] remove the [11,22,33,44,55,66,77,88,99] of these 90 numbers, and there is still 81.
The general term formula is f(k) = 9 * 9 * 8 * ... (9-k + 2), then we can pass the [1, n] interval digits through the general term formula according to the size of n Calculate and add up
Code
Java
public class Count_Numbers_with_Unique_Digits {
class Solution {
public int countNumbersWithUniqueDigits(int n) {
if (n == 0) return 1;
int res = 0;
for (int i = 1; i <= n; ++i) {
res += count(i);
}
return res;
}
int count(int k) {
if (k < 1) {
return 0;
}
if (k == 1) {
return 10;
}
int res = 1;
for (int i = 9; i >= (11 - k); --i) {
res *= i;
}
return res * 9;
}
}
}