357. Count Numbers with Unique Digits

• Difficulty: Medium

• Topics: Math, Dynamic Programming, Backtracking

• Similar Questions:

Problem:

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

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

Solutions:

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        if (n == 1) return 10;
        if (n > 10)    return countNumbersWithUniqueDigits(10);
        return 9 * getUnique(n - 1) + countNumbersWithUniqueDigits(n - 1);
    }

private:
    inline int getUnique(int n) {
        int ret = 1;
        for (int i = 0; i < n; ++i) {
            ret *= (9 - i);
        }

        return ret;
    }

};