# LeetCode 902: Numbers At Most N Given Digit Set

## Problem Restatement

We are given:

- A set of allowed digits as strings.
- An integer `n`.

We may use the given digits any number of times to build positive integers.

We need to count how many numbers are less than or equal to `n`.

For example:

```python
digits = ["1", "3", "5", "7"]
n = 100
```

Valid numbers include:

```python
1, 3, 5, 7,
11, 13, 15, 17,
31, 33, ...
71, 73, 75, 77
```

We count every valid positive integer that does not exceed `100`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `digits` and integer `n` |
| Output | Number of valid integers |
| Digits | Can be reused multiple times |
| Constraint | Every constructed number must be `<= n` |

Function shape:

```python
def atMostNGivenDigitSet(digits: list[str], n: int) -> int:
    ...
```

## Examples

Example 1:

```python
digits = ["1", "3", "5", "7"]
n = 100
```

Answer:

```python
20
```

Explanation:

- 1-digit numbers: `4`
- 2-digit numbers: `4 * 4 = 16`
- No valid 3-digit number is `<= 100`

Total:

```python
4 + 16 = 20
```

Example 2:

```python
digits = ["1", "4", "9"]
n = 1000000000
```

Answer:

```python
29523
```

Example 3:

```python
digits = ["7"]
n = 8
```

Valid numbers:

```python
7
```

Answer:

```python
1
```

## First Thought: Generate Everything

A direct approach is:

1. Generate every possible number using the allowed digits.
2. Keep only numbers `<= n`.

This quickly becomes impossible.

If we have `k` digits and length `m`, the number of possibilities is:

```python
k^m
```

For large `n`, this explodes rapidly.

We need to count mathematically instead of generating explicitly.

## Key Insight

We can split the problem into two parts.

### Part 1: Numbers Shorter Than `n`

Suppose:

```python
n = 3456
```

Every valid number with:

- 1 digit
- 2 digits
- 3 digits

is automatically smaller than `3456`.

So we can count them directly.

If there are `k` allowed digits:

- Length 1: `k`
- Length 2: `k^2`
- Length 3: `k^3`

Total:

```python
k + k^2 + k^3
```

### Part 2: Numbers With Same Length As `n`

Now we count valid numbers digit by digit.

For:

```python
n = 3456
```

we compare from left to right.

At each position:

- Count digits smaller than the current digit of `n`.
- Add all combinations for remaining positions.
- If the exact digit exists, continue.
- Otherwise stop.

This behaves like lexicographic counting.

## Algorithm

Convert `n` into a string:

```python
s = str(n)
```

Let:

```python
m = len(s)
k = len(digits)
```

### Step 1: Count Shorter Numbers

For every length smaller than `m`:

```python
k^length
```

Add all counts together.

### Step 2: Process Equal-Length Numbers

Walk through each digit position.

At position `i`:

1. Count how many allowed digits are smaller than `s[i]`.
2. For each smaller digit, remaining positions can be anything:

```python
smaller_count * (k ^ remaining_positions)
```

3. If `s[i]` itself is not available, stop immediately.
4. Otherwise continue to the next digit.

If we finish all positions successfully, include `n` itself.

## Correctness

Every valid number belongs to exactly one of two groups:

1. Numbers with fewer digits than `n`
2. Numbers with the same number of digits as `n`

The first group is counted completely using combinatorics.

For the second group, we process digits left to right.

At each position, choosing a smaller digit guarantees the constructed number is already smaller than `n`, so remaining positions may contain any allowed digits.

If the current digit of `n` is unavailable, no continuation can match or stay below `n`, so counting stops correctly.

If every digit matches successfully, then `n` itself is valid and must be counted.

No valid number is missed, and no invalid number is added.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(len(n) * len(digits))` | Each position scans all digits |
| Space | `O(1)` | Only constant extra space |

## Implementation

```python
class Solution:
    def atMostNGivenDigitSet(self, digits: list[str], n: int) -> int:
        s = str(n)

        k = len(digits)
        m = len(s)

        answer = 0

        for length in range(1, m):
            answer += k ** length

        for i in range(m):
            current = s[i]

            smaller_count = 0

            for d in digits:
                if d < current:
                    smaller_count += 1

            remaining = m - i - 1

            answer += smaller_count * (k ** remaining)

            if current not in digits:
                return answer

        return answer + 1
```

## Code Explanation

Convert `n` into a string so we can process digits individually:

```python
s = str(n)
```

Count all valid shorter numbers:

```python
for length in range(1, m):
    answer += k ** length
```

Now process equal-length numbers.

At each position:

```python
for i in range(m):
```

we count digits smaller than the current digit:

```python
if d < current:
    smaller_count += 1
```

Every smaller choice allows free selection of remaining positions:

```python
answer += smaller_count * (k ** remaining)
```

If the current digit itself does not exist:

```python
if current not in digits:
    return answer
```

then we cannot continue matching `n`.

If every digit matches successfully, `n` itself is valid:

```python
return answer + 1
```

## Testing

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

    assert s.atMostNGivenDigitSet(["1", "3", "5", "7"], 100) == 20
    assert s.atMostNGivenDigitSet(["1", "4", "9"], 1000000000) == 29523
    assert s.atMostNGivenDigitSet(["7"], 8) == 1
    assert s.atMostNGivenDigitSet(["1", "2", "3"], 3) == 3
    assert s.atMostNGivenDigitSet(["1", "2", "3"], 35) == 12
    assert s.atMostNGivenDigitSet(["5", "7", "8"], 4) == 0

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Sample case | Confirms main logic |
| Very large `n` | Checks scalability |
| Single digit set | Minimal configuration |
| Exact equality | Confirms inclusive counting |
| Mid-range value | Checks digit-by-digit counting |
| No valid numbers | Confirms zero handling |