> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/count-numbers-with-unique-digits.md).

# Count Numbers with Unique Digits

<https://leetcode.com/problems/count-numbers-with-unique-digits/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.

## Thoughts

排列组合，例如n=4则四位数每个数字不相同的个数是9 \* 9 \* 8 \* 7. 由于首位不能是0所以是9而不是10. 由于返回的不止n位数的，还有返回所有0\~n-1位数的所有可能。而三位数为9\*9\*8，因为f(n) = f(n-1) \* j.

## Code

```
  class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        int res = 0;
        if (n == 0) {
            res += 1;
            return res;
        } 
        int[] f = new int[n + 1];
        f[0] = 1;
        f[1] = 9;
        for (int i = 2, j = 9; i <= n && j > 0; i++, j--) {
            f[i] = f[i - 1] * j; 
        }
        for (int i = 0; i <= n; i++) {
            res += f[i];
        }
        return res;
    }
}
```

## Analysis

做题耗时30min.

Errors:

1. 开始误以为直接返回10 \* 9 \* 8 ...即可，但这样少了060这样的数。

时间复杂度为O(n).