# LeetCode 357: Count Numbers with Unique Digits

## Problem Restatement

Given an integer `n`, count how many integers `x` satisfy:

```python
0 <= x < 10**n
```

and have no repeated digits.

A number has unique digits if every digit appears at most once.

Examples:

```text
123 has unique digits
102 has unique digits
11 does not have unique digits
100 does not have unique digits
```

The range includes `0`.

The range does not include `10^n`.

The problem constraints are `0 <= n <= 8`. The official examples include `n = 2`, whose answer is `91`, and `n = 0`, whose answer is `1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | Count of numbers with unique digits |
| Range | `0 <= x < 10^n` |
| Constraint | `0 <= n <= 8` |

Example function shape:

```python
def countNumbersWithUniqueDigits(n: int) -> int:
    ...
```

## Examples

For:

```python
n = 0
```

The range is:

```python
0 <= x < 1
```

Only the number `0` is included.

So the answer is:

```python
1
```

For:

```python
n = 1
```

The range is:

```python
0 <= x < 10
```

The numbers are:

```text
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
```

All have unique digits.

So the answer is:

```python
10
```

For:

```python
n = 2
```

The range is:

```python
0 <= x < 100
```

There are `100` numbers from `0` to `99`.

The repeated-digit two-digit numbers are:

```text
11, 22, 33, 44, 55, 66, 77, 88, 99
```

There are `9` of them.

So the answer is:

```python
100 - 9 = 91
```

## First Thought: Check Every Number

A direct solution is to loop through every number from `0` to `10^n - 1`.

For each number:

1. Convert it to a string.
2. Check whether all characters are distinct.
3. Count it if no digit repeats.

Example:

```python
class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        limit = 10 ** n
        count = 0

        for x in range(limit):
            digits = str(x)

            if len(set(digits)) == len(digits):
                count += 1

        return count
```

This is easy to understand.

But it checks every number, so the time grows as `10^n`.

For `n = 8`, that means checking `100,000,000` numbers.

We need to count directly instead.

## Key Insight

Count valid numbers by their digit length.

For length `0`, we count the number `0`.

For length `1`, the valid numbers are:

```text
0 through 9
```

There are `10`.

For length `2`, the first digit cannot be `0`.

So:

| Position | Choices |
|---|---:|
| First digit | `9` choices: `1` to `9` |
| Second digit | `9` choices: `0` to `9`, except the first digit |

So length `2` contributes:

```python
9 * 9 = 81
```

For length `3`:

| Position | Choices |
|---|---:|
| First digit | `9` |
| Second digit | `9` |
| Third digit | `8` |

So length `3` contributes:

```python
9 * 9 * 8
```

In general, for a fixed length `k >= 1`:

```text
first digit: 9 choices
second digit: 9 choices
third digit: 8 choices
fourth digit: 7 choices
...
```

Then add counts for all lengths from `1` to `n`, plus the number `0`.

## Algorithm

If `n == 0`, return `1`.

Otherwise:

1. Start with `total = 10`, which counts all one-digit numbers: `0` through `9`.
2. Let `current = 9`, representing the count for the current length before adding the next digit.
3. Let `available = 9`, representing how many choices remain for the next digit.
4. For every length from `2` to `n`:
   - Update:

```python
current *= available
```

   - Add `current` to `total`.
   - Decrease `available`.

5. Return `total`.

Since there are only `10` digits, lengths above `10` contribute nothing. For this problem, `n <= 8`, so this does not affect the official constraints.

## Correctness

Every number in the range `0 <= x < 10^n` has at most `n` digits.

The algorithm counts valid numbers by exact digit length.

The number `0` is included in the one-digit count.

For every length `k >= 1`, the first digit has `9` choices because it cannot be `0`. Each later position must use a digit that has not appeared before. Therefore the number of valid `k`-digit numbers is counted by multiplying the number of choices at each position.

These length groups are disjoint because a number has exactly one decimal length, except `0`, which is already included in the base count.

The algorithm sums the counts for all lengths up to `n`, so it counts every valid number in the required range exactly once.

Therefore, the returned value is correct.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | One loop from length `2` to `n` |
| Space | `O(1)` | Only a few counters are stored |

With `n <= 8`, this is constant in practice.

## Implementation

```python
class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        if n == 0:
            return 1

        total = 10
        current = 9
        available = 9

        for length in range(2, n + 1):
            current *= available
            total += current
            available -= 1

        return total
```

## Code Explanation

The case `n = 0` means the range is only:

```python
0 <= x < 1
```

So only `0` is counted:

```python
if n == 0:
    return 1
```

For `n >= 1`, all one-digit numbers are valid:

```python
total = 10
```

The variable `current` stores how many valid numbers have the current length.

Before length `2`, we start with:

```python
current = 9
```

This represents the first digit choices: `1` through `9`.

The next digit has `9` choices:

```python
available = 9
```

For each new length:

```python
current *= available
```

This adds one more digit position.

Then:

```python
total += current
```

adds all valid numbers of that length.

Finally:

```python
available -= 1
```

because one more digit has been used.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.countNumbersWithUniqueDigits(0) == 1
    assert s.countNumbersWithUniqueDigits(1) == 10
    assert s.countNumbersWithUniqueDigits(2) == 91
    assert s.countNumbersWithUniqueDigits(3) == 739
    assert s.countNumbersWithUniqueDigits(4) == 5275
    assert s.countNumbersWithUniqueDigits(8) == 2345851

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `n = 0` | Checks the special range `[0, 1)` |
| `n = 1` | All single-digit numbers are valid |
| `n = 2` | Official example |
| `n = 3` | Checks multiplication by decreasing choices |
| `n = 4` | Checks accumulated total |
| `n = 8` | Checks upper constraint |