357. Count Numbers with Unique Digits

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

假設f(n)是表示count of numbers with unique digits of length n，那本題所求就是f(1) + f(2) + ... + f(n)。 f(1) = 10，如果只有一個digit，那符合條件的數有0, 1, 2, ... , 9。 f(2) = 9 * 9，2個digits的數ij，i不能是0，只能從1-9去選數字，所以有9種可能，j不能是i選過的數字，所以從0-9減去i選過的數字，所以也有9種可能，總共是9 * 9 個數符合條件。 f(3) = f(2) * 8，3個digits的數字ijk，ij的情況可以從f(2)得到，k可以從0-9中扣掉i和j選過的數字之後選擇，所以有8種可能。總共就是9 * 9 * 8個符合的情況。 f(4) = f(3) * 7，4個digits的數字ijkl，ijk可以從f(3)得到，l可以從0-9扣掉i, j, k選過的數字之後選擇，所以有7種可能。總共是9 * 9 * 8 * 7個符合的數字。 ...... f(10) = 9 * 9 * 8 * 7 * ... * 2 * 1 f(11) = 0 = f(12) = f(13) = ... n > 10之後f(n)都是0。

// Math + Dynamic Programming
int countNumbersWithUniqueDigits(int n) { // time: O(1); space: O(1)
    if (n == 0) return 1;
    int res = 10, uniq = 9, avai = 9;
    while (n-- > 1 && avai > 0) {
        uniq *= avai;
        res += uniq;
        --avai;
    }
    return res;
}