Numbers At Most N Given Digit Set: Digit DP Pattern

Given a sorted array of digit strings digits (each element is a string like "1", "3", etc.) and a positive integer n, return the count of positive integers that can be formed using only those digits and are <= n. You may reuse digits as many times as you want, and numbers must not have leading zeros.

This is LeetCode 902: Numbers At Most N Given Digit Set. It is a hard problem that looks daunting at first, but once you split it into two clean subproblems, the logic becomes surprisingly compact. The core technique is digit DP, which counts numbers by building them one digit at a time while respecting an upper bound.

For digits = ["1","3","5","7"] and n = 100, the answer is 20. There are 4 one-digit numbers (1, 3, 5, 7), 16 two-digit numbers (11, 13, 15, ..., 77), and 0 three-digit numbers that fit under 100.

Why this problem matters

Digit DP is one of those patterns that shows up rarely enough that people forget it, but frequently enough that it can decide an interview. Any problem that asks "how many numbers in some range satisfy a digit-level constraint?" likely uses this technique. Examples include counting numbers with specific digit sums, numbers that avoid certain digits, and numbers that match a pattern.

The mental model you build here transfers directly to those problems. The key idea is always the same: split the count into numbers with fewer digits (pure combinatorics) and numbers with the same number of digits (digit-by-digit comparison against the bound).

The key insight

Every valid number falls into one of two categories:

1. Shorter than N: if N has k digits, then any number with fewer than k digits is automatically <= n. For length i, there are D^i valid numbers (where D is the size of the digit set). You just sum these up for i from 1 to k - 1.

2. Same length as N: you must build the number digit by digit, comparing each position to the corresponding digit of N. At each position, digits strictly less than the corresponding digit of N are "free", meaning all remaining positions can be anything. Digits equal to N's digit keep you on a "tight" path. Digits greater than N's digit are invalid.

This split is the backbone of every digit DP problem. The shorter-length count is pure math, and the same-length count is a single left-to-right scan.

The solution

def atMostNGivenDigitSet(digits, n):
    s = str(n)
    k = len(s)
    D = len(digits)

    result = sum(D ** i for i in range(1, k))

    for i in range(k):
        found_equal = False
        for d in digits:
            if d < s[i]:
                result += D ** (k - i - 1)
            elif d == s[i]:
                found_equal = True
        if not found_equal:
            return result

    return result + 1

Here is what each piece does:

1. Convert N to its string representation so you can compare digit by digit.
2. Count shorter numbers: for lengths 1 through k - 1, each position has D choices, giving D^1 + D^2 + ... + D^(k-1) total numbers.
3. Count same-length numbers: scan the digits of N from left to right. At each position, count how many digits in the set are strictly less than N's digit (each contributes D^remaining numbers). If a digit matches N's digit exactly, continue to the next position. If no digit matches, stop, because you cannot build N itself or any number with this prefix.
4. Handle N itself: if you made it through all positions with a match at every step, N itself is a valid number, so add 1.

Visual walkthrough

The walkthrough confirms the count: 4 one-digit numbers, 16 two-digit numbers, and 0 three-digit numbers. The tight path for three-digit numbers dies at the second position because no digit in the set is <= 0.

Complexity analysis

Time: you convert N to a string of length k = O(log N), then for each of the k positions you scan through D digits. Total work is O(k * D). Computing D^i values also takes O(k) time.

Space: the string representation of N takes O(log N) space. No DP table is needed since you only track a running count and whether you are on the tight path.

The building blocks

1. Counting shorter numbers with combinatorics

For any number with fewer digits than N, every position is a free choice from D options. This is the same counting principle you use when computing how many strings of length i you can form from an alphabet of size D:

total_shorter = sum(D ** i for i in range(1, k))

This pattern applies whenever you need to count all strings of a given length from a fixed alphabet. It shows up in combinatorics-heavy problems like counting binary strings, generating permutations, and base conversion.

2. Digit-by-digit comparison (tight bound)

The left-to-right scan compares your number to N one digit at a time. At each position, you decide: go lower (freedom for all remaining positions), match exactly (stay tight), or exceed (impossible, stop). This is the heart of digit DP:

for i in range(k):
    for d in digits:
        if d < s[i]:
            result += D ** (k - i - 1)
        elif d == s[i]:
            found_equal = True
    if not found_equal:
        return result

This scan pattern is reusable for any problem where you count numbers up to a bound by processing digits left to right. The "tight" flag controls whether remaining digits are free or constrained.

Edge cases

• All digits greater than N's first digit: for example digits = ["3","5"] and n = 2. No same-length number is valid. The answer is purely from shorter lengths, which in this case is 0 since N has only 1 digit. Answer: 0.
• N itself is constructible: digits = ["1","2"] and n = 21. The tight path succeeds through all positions, so you add 1 for N itself.
• Single-digit N: digits = ["1","3","5","7"] and n = 5. No shorter-length numbers exist. Just count digits <= 5: that is 1, 3, 5, giving 3.
• All digits the same: digits = ["1"] and n = 111. Shorter: 1^1 + 1^2 = 2. Same length: tight path succeeds (1 matches at every position), add 1. Total: 3 (the numbers 1, 11, 111).
• Digit "1" with large N: digits = ["1"] and n = 1000000000. The answer is just the number of digits in N, since the only numbers are 1, 11, 111, 1111, etc. That gives 9.

From understanding to recall

You have read the solution and it makes sense. Split into shorter numbers (easy combinatorics) and same-length numbers (digit-by-digit scan). But can you write it from scratch without looking?

The details matter: using D ** (k - i - 1) for the free subtree size, remembering to check found_equal at each position, and adding 1 at the end if the tight path completes. These are small things that are easy to mix up under pressure if you have not practiced writing them from memory.

Digit DP problems are rare enough that you might not encounter one for months, then suddenly face one in an interview. Spaced repetition keeps the pattern fresh. You practice writing the combinatorics sum and the digit scan from scratch at increasing intervals until the code flows without hesitation.

Related posts

• Counting Bits - Another problem that uses bit-level structure for counting, similar mindset to digit-level analysis
• Number of Digit One - Classic digit DP that counts occurrences of a specific digit across a range
• Permutations - Backtracking and counting, the brute-force alternative to the combinatorial approach used here

CodeBricks breaks the digit DP pattern into its combinatorial counting and digit-by-digit comparison building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a digit DP question shows up in your interview, you do not think about it. You just write it.