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:

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

Valid numbers include:

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

Function shape:

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

Examples

Example 1:

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

Answer:

20

Explanation:

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

Total:

4 + 16 = 20

Example 2:

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

Answer:

29523

Example 3:

digits = ["7"]
n = 8

Valid numbers:

7

Answer:

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:

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:

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:

k + k^2 + k^3

Part 2: Numbers With Same Length As n

Now we count valid numbers digit by digit.

For:

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:

s = str(n)

Let:

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

Step 1: Count Shorter Numbers

For every length smaller than m:

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:

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

Implementation

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:

s = str(n)

Count all valid shorter numbers:

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

Now process equal-length numbers.

At each position:

for i in range(m):

we count digits smaller than the current digit:

if d < current:
    smaller_count += 1

Every smaller choice allows free selection of remaining positions:

answer += smaller_count * (k ** remaining)

If the current digit itself does not exist:

if current not in digits:
    return answer

then we cannot continue matching n.

If every digit matches successfully, n itself is valid:

return answer + 1

Testing

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: