357. Count Numbers with Unique D

Description

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

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;
    }
}