# 357 Count Numbers with Unique Digits

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]`)

**The Idea:**

* If `n == 0`, we can only chose $$10^0 = 1$$ or just one thing.
* When `n == 1`, we can choose $$0 \leq x < 10$$ things, that is $$0,1,2,3,4,5,6,7,8,9$$ things
* When `n == 2`, we can choose a permutation of 2 things, that is...

```
01, 02, 03 ... 09
12, 13, 14 ... 19
21, 23, 24 ... 29
```

* Which equates to `P(10, 2)` things. But we have some redundancy, that is those 0's in the beginning, which are effectively the same thing as `0,1,2,3,4,...9`. To get rid of these, we subtract `P(9,1)` to get rid of just those 9 elements.
* When `n == 4`, we can likewise chose `P(10,4)` things. But what is the redundancy here. Lets think about it.

```
012, 013, .. 019
021, 023, .. 029
031, 032, .. 039

...

091, 092, .. 098
```

* We find 9 elements per row, for 8 rows. This follows `9*8`, or `P(9,2)`
* It then follows that the number of numbers of unique Digits are $$\sum\_{i=1}^n{P(10, i) - P(9, i - 1)}$$

```cpp
int permutation(int num, int choose)
{
    int cur = 1;
    int go_to = num - choose;
    for (int i = num; i > go_to; i--)
        cur *= i;

    return cur == 1 ? 0 : cur;
}

int countNumbersWithUniqueDigits(int n) 
{
    if (n == 0) return 1;
    int prev_perm = 0;
    for (int i = 1; i <= n; i++) {
        prev_perm += permutation(10, i) - permutation(9, i - 1);
    }

    return prev_perm;
}
```