Description
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.
Solution
Mathematics & DP, O(n), S(1)
这道题的目的是构造不超过n位的数字val，使得val中每位都是unique的。其实就是数学概率题啊，也可以用DP解决。
首先需要注意一点的是，第一位选择0怎么办，这样数字就会不足n位。其实只要按照数字位数digits增长，从1到n讨论就行了，这样就能保证第一个digit不选择0。
用dp[i]代表i个digits对应的unique digits num个数。那么：
- dp[0] = 1; // 0
- dp[1] = dp[0] * 9 // [1, 9]
- dp[i] = dp[i - 1] * (10 - (i - 1)) = dp[i - 1] * (11 - i) // select a digit from [0, 9], except digits used in dp[i - 1]
class Solution {
public int countNumbersWithUniqueDigits(int n) {
if (n < 0) {
return 0;
}
int prev = 1;
int sum = 1;
for (int i = 1; i <= n && prev > 0; ++i) {
if (i == 1) {
prev *= 9;
} else {
prev *= 11 - i;
}
sum += prev;
}
return sum;
}
}
