# LeetCode 1012: Numbers With Repeated Digits

## Problem Restatement

We are given an integer `n`.

We need to return the count of positive integers up to `n` (inclusive) that have at least one repeated digit.

The official constraints state that `1 <= n <= 10^9`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | Count of integers in `[1, n]` with at least one repeated digit |

Function shape:

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

## Examples

Example 1:

```python
n = 20
```

Numbers with repeated digits in `[1, 20]`: `11`.

Answer:

```python
1
```

Example 2:

```python
n = 100
```

Numbers with repeated digits: `11, 22, 33, ..., 99` (9 numbers).

Answer:

```python
10
```

Wait: also `100` has no repeated digits (digits 1, 0, 0 → 0 is repeated). So answer is `10`.

## Key Insight

It is easier to count numbers with **no repeated digits** and subtract from `n`.

Count integers in `[1, n]` with all distinct digits.

This breaks into:
1. All numbers with fewer digits than `n` (all distinct digits).
2. Numbers with the same number of digits as `n` but digit-by-digit bounded by `n`.

## Algorithm

Let `digits` be the list of digits of `n`.

Let `L = len(digits)`.

**Step 1**: Count distinct-digit numbers with fewer than `L` digits.

For a `k`-digit number (`k < L`):

- The first digit has `9` choices (1-9).
- The second digit has `9` choices (0-9 minus first).
- The third has `8` choices, etc.

Count = `9 * P(9, k-1)` where `P(n, k) = n! / (n-k)!`.

**Step 2**: Count distinct-digit numbers with exactly `L` digits that are `<= n`.

Walk digit by digit. For each position `i`:

- Choose a digit `d` from `0` to `digits[i] - 1` (or `1` to `digits[i] - 1` for the first).
- `d` must not be already used.
- The remaining positions can be any of the unused digits.

For each valid prefix smaller than `n`'s prefix, count permutations of the remaining positions using unused digits.

Sum these up, then subtract from `n` to get the answer.

## Correctness

Every positive integer has either distinct digits or at least one repeated digit.

Counting distinct-digit integers precisely and subtracting from `n` gives the count of integers with at least one repeated digit.

The digit-by-digit enumeration ensures we count every distinct-digit integer up to `n` exactly once.

## Edge Cases

- Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
- Confirm the iteration order matches the recurrence dependencies.
- For optimization DP, separate impossible states from valid states with value `0`.

## Complexity

Let `L = len(str(n))`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(L^2)` | At most `L` positions, each with at most `10` digit choices |
| Space | `O(L)` | Digit array and used set |

## Common Pitfalls

- Do not overwrite a state before all transitions that still need the old value have used it.
- Use the problem constraints to choose between full tables and compressed state.

## Implementation

```python
from math import perm

class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        digits = list(map(int, str(n)))
        L = len(digits)
        count = 0

        # Count distinct-digit numbers with fewer digits
        for k in range(1, L):
            count += 9 * perm(9, k - 1)

        # Count distinct-digit numbers with L digits, <= n
        used = set()
        for i, d in enumerate(digits):
            start = 1 if i == 0 else 0
            for x in range(start, d):
                if x not in used:
                    count += perm(9 - i, L - i - 1)
            if d in used:
                break
            used.add(d)
        else:
            count += 1  # n itself has distinct digits

        return n - count
```

## Code Explanation

Count distinct-digit numbers shorter than `n`:

```python
for k in range(1, L):
    count += 9 * perm(9, k - 1)
```

`perm(9, k-1)` counts ways to fill positions 2 through k from 9 remaining digits.

Walk digit by digit and count valid prefixes:

```python
for x in range(start, d):
    if x not in used:
        count += perm(9 - i, L - i - 1)
```

For each digit `x` less than `digits[i]` (and not already used), we can freely place `L - i - 1` more distinct digits.

After the loop, if all prefix digits were distinct (the `else` branch), `n` itself is a distinct-digit number:

```python
else:
    count += 1
```

Finally subtract from `n` to count numbers with repeated digits:

```python
return n - count
```

## Testing

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

    assert s.numDupDigitsAtMostN(20) == 1
    assert s.numDupDigitsAtMostN(100) == 10
    assert s.numDupDigitsAtMostN(1000) == 262
    assert s.numDupDigitsAtMostN(1) == 0
    assert s.numDupDigitsAtMostN(11) == 1

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `20` | `1` | Only `11` has repeated digits |
| `100` | `10` | `11,22,...,99,100` |
| `1000` | `262` | Verified by enumeration |
| `1` | `0` | Single digit, no repeats |
| `11` | `1` | Only `11` has a repeated digit |